Question 3.36: Define f : N → N by f(0) = 0, f (1) = 1, and f(n) =f(n - 1) ......
Define f:\mathbb{N}\to\mathbb{N} by f(0) = 0, f (1) = 1, and f(n) =f(n – 1) +f(n – 2) for n ≥ 2. Prove that
(a) f(i) < f(i + 1) for all i ≥ 2;
(b) there exist precisely four i ∈ \mathbb{N} with ( f ο f ) ( i ) = f ( i ) .
Writing f_{n} for f(n), prove also that
(c)f_{5n} is divisible by 5;
(d) f_{n+2}=1+\sum_{i=1}^{n}f_{i};
(e) f_{n-1}f_{n+1}-f_{n}^{2}=(-1)^{n}\,\mathrm{for}\,n\geq 1\,;
(f) 2^{n}f_{n}=[(1+{\sqrt{5}})^{n}-(1-{\sqrt{5}})^{n}]/{\sqrt{5}}.
(a) Since we have 1=f(2)\lt f(3)=2 the result holds for i = 2. By way of applying the second principle of induction, suppose that the result holds for 2\leqslant i\leqslant n. Then we have
f(n+1)=f(n)+f(n-1)\\ \lt f(n+1)+f(n)\\ =f(n+2),whence we see that it also holds for n + 1.
(b) If f\left[f(i)\right]=f(i) then, by (a), if i > 2 we must have f(i) = i and the only possibility is i = 5; and if i\leqslant2 then it is readily seen that the possibilities are i = 0, 1,2.
(c) For n = 1 we have f_{5}=5. Assume by way of induction that the result holds for n. Then
f_{5(n+1)}=f_{5n+5}=f_{5n+4}+f_{5n+3}\\ =2f_{5n+3}+f_{5n+2}\\ =3f_{5n+2}+2f_{5n+1}\\ =5f_{5n+1}+3f_{5n},whence it also holds for n + 1.
(d) Since f_{3}=2=1+f_{1}, the result holds for n = 1. Assume by way of induction that it holds for n, so that f_{n+2}=1+\Sigma_{i=1}^{n}f_{i}. Then we have
f_{n+3}=f_{n+2}+f_{n+1}\\ =1+\sum_{i=1}^{n}f_{i}+f_{n+1}\\ =1+\sum_{i=1}^{n+1}f_{i},whence it also holds for n + 1.
(e) The result is clearly true for n = 1. Assume by way of induction that the result holds for n, so that f_{n-1}f_{n+1}-f_{n}^{2}=(-1)^{n}. Then we have
f_{n}f_{n+2}-f_{n+1}^{2}=f_{n}(f_{n}+f_{n+1})-f_{n+1}^{2}\\ =f_{n}^{2}+f_{n}f_{n+1}-f_{n+1}(f_{n}+f_{n-1})\\ =f_{n}^{2}-f_{n+1}f_{n-1}\\ =(-1)^{n}(-1)\\ =(-1)^{n+1},whence it also holds for n + 1.
(f) The result clearly holds for n = 1. By way of applying the second principle of induction, suppose that it holds for all n\leqslant k. Then we have
2^{k+1}\sqrt{5}\,f_{k+1}=2^{k+1}\,\sqrt{5}\,f_{k}+\,2^{k+1}\,\sqrt{5}\,f_{k-1} =2(1+{\sqrt{5}})^{k}-2(1-{\sqrt{5}})^{k}\\ +\,4(1+{\sqrt{5}})^{k-1}-4(1-{\sqrt{5}})^{k-1}\\ =(1+\sqrt{5})^{k-1}(2+2\sqrt{5}+4)\\ -(1-{\sqrt{5}})^{k-1}(2-2{\sqrt{5}}+4)\\ =(1+{\sqrt{5}})^{{\frac{1}{k}}+1}–(1-{\sqrt{5}})^{k+1},whence we see that the result holds also for n = k + 1.