# Proof by induction for Fibonacci numbers

How can we prove by induction the following?

$F_{n+1} = \left\{ \begin{array}{l l} F_{n/2}^2+F_{(n+2)/2}^2 & \quad \text{if$n$is even}\\ F_{(n-1)/2}F_{(n+1)/2}+F_{(n+1)/2}F_{(n+3)/2} & \quad \text{if$n$is odd }\\ \end{array} \right.$

I know that even number is $2m$ and odd number is $2m+1$.

-
i know, it was also my question, but i didnot get any answer, thats why i am posting it again. – doniyor Nov 24 '12 at 19:31
Don't do that. This is what you do if you don't get an answer. – Willie Wong Nov 26 '12 at 9:48
okay, thanks :D – doniyor Nov 28 '12 at 9:39

## 2 Answers

First, define the Fibonacci numbers:

Let $F_n$ be the sequence of Fibonacci numbers, given by

$$F_0 = 0, F_1 = 1, \text{ and}\quad F_n = F_{n-1} + F_{n-2}\; \text{ for}\; n \geq 2.$$

Hints:

$(1)$ Use the definition of $F_n$.

• E.g., $F_{n+1} = F_{n} + F_{n-1}$

$(2)$ You can use the following good-to-know identities:

i) $F_{n-1}^2 + F_n^2 = F_{2n}$.

ii) $F_{n-1}F_n + F_n F_{n+1} = F_{2n+1}$.

Note that the above identities follow from the more general identity:

$(I)$: For $n, m \in \mathbb{N}$: $$F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$$

Proof of $(I)$:

Fix $n \in \mathbb{N}$. We shall use induction on $m$. For $m=1$, the right-hand side of the equation becomes $$F_{n-1}F_{1} + F_{n}F_{2} = F_{n-1} + F_{n},$$ which is equal to $F_{n+1}$. When $m=2$, the equation is also true.( I hope you can prove this!).

Now assume, that the result is true for $k=3,4, \cdots , m$. We want to show that the result is true for $k=m+1$. $$\text{For} \ k=m-1 \ \text{we have} \quad F_{n+m-1} = F_{n-1}F_{m-1} + F_{n}F_{m},\,\text{ and}$$ $$\text{For} \ k = m \ \text{we have} \quad F_{m+n}=F_{n-1}F_{m} + F_{n}F_{m+1}$$ Adding both the sides you will get $$F_{m+n-1} + F_{m+n} = F_{m+n+1} = F_{n-1}F_{m+1} + F_{n}F_{m+2},$$ $$\text{so,}\;\; F_{m+n}=F_{n-1}F_m + F_{n}F_{m+1}$$

Identities (i) and (ii) follow from $(I)$ by putting $m = n$ and manipulating the expressions.

-
doniyor: Can you see how these identities can be useful to your problem? Where, exactly, are you stuck? What can you take to be your base case(s)? – amWhy Nov 24 '12 at 20:58
Sorry to see it late, wow, very nicely explained! i didnot know that good-to-know things – doniyor Nov 25 '12 at 3:59
i thought, i will take as base case for even numbers the number $2n$, then the inductive step to $2n+2$. and for odd numbers, i will take as base case the $3n$ and the inductive step $2n+3$, is it okay? – doniyor Nov 25 '12 at 4:36
no, the inductive step for evens will be $2n-2$ and $2n$ and by adding them, right? – doniyor Nov 25 '12 at 4:48
I think you've got it, but it could also help to express n in terms of an integer m: n = 2m (for even n), n = 2m+1 for odd n. Then you can use induction on m: so for even n, n+2 = 2(m + 1), and for odd n, n+2 = 2(m+1) + 1. That way, e.g., $(F_{n/2})^2 + (F_{(n+2)/n})^2 = (F_{2m/2})^2 + (F_{(2k + 2)/2})^2 = (F_m)^2 + (F_{m+1})^2$...for even n. It simplifies the expression of the $F_i$, likewise for odd n, you can get rid of the fractions. But working with n is fine, though perhaps more confusing. – amWhy Nov 25 '12 at 17:23
show 2 more comments

Do the following:

1. Check that it holds for the base case.
2. Assume that it holds for all <= 2n (can probably be weakened) .
3. You then have that for 2n+1 $$F_{2n+1} = F_{2n}+F_{2n-1} = F^2_n+F^2_{n+1}+F_{n-1}F_{n} +F_nF_{n+1} = F_n(F_n+F_{n-1})+F_{n+1}(F_n+F_{n+1})=F_nF_{n+1}+F_{n+1}F_{n+2}.$$
4. Do a similar manipulation for 2n+2 , using what we just proved for 2n+1. You're done.
-
 but 2n+1 is an odd number, shouldnot be the step 3, 2n+2 ? – doniyor Nov 25 '12 at 5:27 honestly, i dont understand your calculation ways.. why $F_{2n}=F_{n}^{2}+F_{n+1}^{2}$ ?.. shouldnot it be $F_{2n}=F_{n}^{2}+F_{n-1}^{2}$ ? – doniyor Nov 25 '12 at 5:54 i am pulling out my hair, can you please explain your logic? – doniyor Nov 25 '12 at 6:15