官术网_书友最值得收藏!

習題

3.1 求下列表達式的閉式表達式,見式(3-3)。

3.2 用歸納法證明鴿籠原理(例3.19),用|Y|代替|X|進行歸納。

3.3 用歸納法證明擴展鴿籠原理(定理1.3和定理1.4)。

3.4(a)使用∑表示對2的前n個奇數冪求和(即項為21、23等),并用歸納法證明其和是

(b)使用表示2的前n個負整數的冪的乘積(即因子為2-1、2-2等),求乘積的值。

3.5 對于任意的n≥0,用歸納法證明

3.6 對于任意的n≥0,設

我們要證明Sn)總是小于2的,且當n足夠大時,它趨近于2。

(a)S(0)、S(1)、S(2)、S(3)都等于什么?

(b)推測Sn)的通用公式,形式如下:

S(n)=2-…

(c)用歸納法證明,該公式對于所有的n≥0都是正確的。

(d)設ε是一個非常小的正實數。n為多大時,Sn)可以達到2的ε鄰域內?

3.7 對于任意的n≥0,用歸納法證明

3.8 對于任意的n≥1,用歸納法證明

3.9 指出下面證明中的漏洞。

所有的馬都是相同的顏色

歸納基礎。考慮只有一匹馬的集合。只有一匹馬意味著這匹馬和它自己是同樣顏色的,所以命題成立。

歸納假設。假設對于所有n≥1的馬的集合,所有的馬都是相同的顏色。

歸納步驟。證明“對于所有n+1匹馬的集合,在同一個集合中的所有馬都是相同的顏色”,設一個有n+1匹馬的集合如下:

H={h1,h2,…,hn,hn+1}

H有兩個不同的子集:

A={h1,h2,…,hn}

B={h2,…,hn,hn+1}

由于AB都是n個元素的集合,所以在每個集合中,所有馬都是相同顏色的。由于hn+1h2的顏色相同(因為兩者都在B集合中),h2(也在A集合中)與A集合中的其他馬是相同的顏色。因此,hn+1A集合中的所有馬是相同的顏色,所以H集合中的所有馬肯定都是相同的顏色。

因此,對于任意大小的馬的集合,同一集合中的所有馬都是相同的顏色。

3.10 如果相繼兩個元素之間的差每向后一步就會增加1,那么512真的會出現在求和公式(3-2)中最后一個數的位置上嗎?

3.11 證明下面有關Thue序列的結論。

(a)對于任意的n≥1,T2n是一個回文字符串(palindrome),即一個字符串正讀和反讀都是相同的。

(b)對于任意的n,如果同步將Tn中的0換為01、1換為10,可得到Tn+1。這意味著在無窮的Thue位串t0t1…中,也會同步發生上述替換,那么還會得到一個無窮的Thue位串。

3.12 證明:數學歸納法原理比實際需要更通用。也就是說,數學歸納法能證明的命題,弱數學歸納法原理也可以證明:

如果P(0)為真,并且對于任意的nP(n)為真時P(n+1)為真,那么對于所有的nP(n)為真

在數學歸納法中,當固定n0的值為0時,我們稱之為弱歸納法。


[1] 我們在公式中使用(2i+1)來表示項,括號的作用是避免歧義,即我們是對整個表達式求和,不是僅對其中的2i求和(見下式),此值與原式不相同。

[2] 二進制數字,它們是小的信息塊。

[3] 以挪威數學家AxelThue(1863—1922)的名字命名,名字的發音為“Too-eh”。有時也稱之為Thue-Morse序列或Thue-Morse-Prohet序列,得名于美國數學家Marston Morse(1892—1977)以及法國數學家Eugène Prouhet(1819—1967)。早在1851年,Eugène Prouhet就使用了這個序列。

主站蜘蛛池模板: 西青区| 文成县| 闸北区| 沙河市| 台东县| 中江县| 武汉市| 澎湖县| 定远县| 武夷山市| 克东县| 甘洛县| 北宁市| 广昌县| 治多县| 淄博市| 巴林右旗| 牟定县| 法库县| 广安市| 丰都县| 平乐县| 安西县| 洪雅县| 酉阳| 哈密市| 芦山县| 贺州市| 封丘县| 鸡东县| 荆州市| 谢通门县| 广西| 宜兰县| 平武县| 高邮市| 龙游县| 凌云县| 淅川县| 新乡县| 绥阳县|