Let f (n) denote the nth term of a sequence of integers given by the equation f(n) = f(n-1) +f(n-2) for n 2 and f(1) = 1 and f(2) = 1, then using principle of mathematical induction, show that √ 5 f( n ) = {(1+ √ 5) / 2} n -- {(1 -- √ 5) / 2}n for all n = 1

Question

Let f (n) denote the nth term of a sequence of integers given by the equation f(n) = f(n-1) +f(n-2) for n > 2 and f(1) = 1  and f(2) = 1, then using principle of mathematical induction, show  that √ 5 f( n ) = {(1+ √ 5) / 2} n  -- {(1 -- √ 5) / 2}n  for all n > = 1

anonymous · Answer

$$f(n)=f(n-1)+f(n-2),~~n>2\
f(1)=1, ~f(2)=1$$
And you have to show that
$$\sqrt5f(n)=\frac{1+\sqrt5}{2}n-\frac{1-\sqrt5}{2}n,~~\text{for }n\ge1$$
(You have $\left\{f(n)\right\}=\left\{1,1,2,3,5,8,13,21,...\right\}$, which happens to be the Fibonacci sequence.)

First show that the equality holds for $n=1$:
$$\sqrt5f(1)=\frac{1+\sqrt5}{2}-\frac{1-\sqrt5}{2}\
\sqrt5=\frac{\sqrt5+\sqrt5}{2}\
\sqrt5=\sqrt5$$
Now assume it holds for $n=k$:
$$\sqrt5f(k)=\frac{1+\sqrt5}{2}k-\frac{1-\sqrt5}{2}k$$
 and, under this assumption, show that it holds for $n=k+1$:
$$\sqrt5f(k+1)=\frac{1+\sqrt5}{2}(k+1)-\frac{1-\sqrt5}{2}(k+1)$$
What do you know about $f(k+1)$, and how can you rewrite the last equation so that it uses the hypothesis that the equality holds for $k$ ?