F(n)??01??F?n?1? 当n?1时，????11? F(n)F(n?1)????n
解：用数学归纳法证明：
?F(0)F(1)??01?当n=1时，????12?成立； F(1)F(2)????F(k)??01??F(k?1)设 当n=k时，????11?成立； F(k)F(k?1)????kF(k?1)??F(k)F(k)?F(k?1)??F(k)则 当n=k+1时，????F(k)?F(k?1)F(k?1)?F(k)?
F(k?1)F(k?2)????F(k)??01??01??01??01??F(k?1) ???*?11???11?*?11???11?F(k)F(k?1)??????????kk?1
也就是说，当n=k+1时，成立，证毕。
12. 考虑基于定义计算第n个Fibonacci数的递归算法F(n):
算法 F(n)
//根据定义，递归计算第n个Fibonacci数 //输入：一个非负整数n //输出：第n个Fibonacci数 if n <= 1 return n
else return F(n-1) + F(n-2)
令C(n)和Z(n)分别是F(n)调用F(1)和F(0)的次数，试证明： 1）C(n) = F(n) 2）Z(n) = F(n-1)
解：用数学归纳法证明：
当n=1时，C（n）= 1 = F（1）， Z（n） = 0 = F（0）成立； n=2时，C（n）= 2 = F（2）， Z（n） = 1 = F（1）成立； 假设 当n=k-1时，有C(k-1) = F(k-1)， Z(k-1) = F(k-2) 成立；
当n=k时，有C(k) = F(k)， Z(k) = F(k-1) 成立；
则 当n=k+1时，F（k+1）= F（k）+ F（k-1），
那么， C（k+1）= C（k）+ C（k-1）= F（k）+ F（k-1） = F（k+1） Z（k+1）= Z（k）+ Z（k-1）= F（k-1）+ F（k-2） = F（k） 也就是说，当n=k+1时，成立，证毕。
13. 当两个连续Fibonacci数F(n)和F(n-1)作为Euclidean algorithm for greatest common divisor (GCD)的输入时，该算法需要做多少次求模运算？
解：F（n）= F（n-1）+ F（n-2）， 也就是说
m <- F（n)、 n <- F（n-1）、 r <- F（n-2）； 又F（n）mod F（n-1）= F（n-2）；于是， r从F（n-2）一直倒退到0 求模运算做了 n-2+1=n-1 次。
14. 试证明：
当n?1时, F(n+1)?F(n-1) – (F(n))2 = (-1)n
解：由11题得：
F(n)??01??F?n?1???当n?1时，? ??F(n?1)??11??F(n)n
展开即得：当n?1时, F(n+1)?F(n-1) – (F(n))2 = (-1)n
15. 给定n，试问有多少个仅由1和2组成的序列（每个序列的和为n）。如当n=4时，有5个序列（每个序列和为4）：
1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2
解：多次计算可知 F(n)?F(n?1)?F(n?2)，
也就是说，他们的个数组成Fibonacci数列；
个数为：