習題

4.1 設a₁=0、a₂=6、a₃=9。對于n>3,a_n=a_n-1+a_n-3。證明對于所有n，a_n可被3整除。

4.2 證明對于所有的n≥8，存在整數a和b，使得n=3a+5b，即n是多個3與多個5的和。

4.3 證明對于任意的n>1，可以使用由三個正方形組成的L形磚片（見圖4.13）平鋪一個2ⁿ×2ⁿ正方形，只留角上有一個空白的正方形（見圖4.14）。其中，L形磚片可以以任何方向旋轉和使用。

4.4 假設已知實數x，使得是整數。應用強歸納法證明：對于任意整數，都有是整數。

提示：將乘積展開找到一個有助于歸納的等式。

4.5 設S是一個數列a₁,a₂,a₃,…，其中a₁=1、a₂=2、a₃=3，并且對于任意的n≥4，有a_n=a_n-1+a_n-2+a_n-3。應用強歸納法證明：對于任意的正整數n，有a_n<2ⁿ。

4.6 證明：能夠用強歸納法證明的任意命題都可以用基本歸納法證明。

4.7 證明：質分解式是唯一的，即如果有

其中p_i、r_i都是遞增的質數，且所有指數e_i、f_i都是正整數，那么存在k=l，對于每個i，有p_i=r_i、e_i=f_i。

4.8（a）證明：數學歸納法蘊含良序原理。提示：對非負整數的非空集合的大小進行歸納，假設“如果一個集合非空，那么就能找到它的一個成員”。

（b）證明：良序原理蘊含數學歸納法。提示：假設P（n₀）為真，并且對于每一個n，有“如果P（n）為真，則P（n+1）為真”。由于某些原因，P（n）不是對于所有的n≥n₀都為真。關于非負整數集合中P為假的原因。

4.9 應用算術基本定理證明中給出的方法，找到100的質分解式。展示每個階段的S、p和q的值。

4.10 假設你能買到的郵票只有2美分和3美分兩種面值。證明只要n≥2，n美分的郵費最多使用張郵票。