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$.

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

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.$$


$(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.

  • $\begingroup$ 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)? $\endgroup$ – Namaste Nov 24 '12 at 20:58
  • $\begingroup$ Sorry to see it late, wow, very nicely explained! i didnot know that good-to-know things $\endgroup$ – doniyor Nov 25 '12 at 3:59
  • $\begingroup$ 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? $\endgroup$ – doniyor Nov 25 '12 at 4:36
  • $\begingroup$ no, the inductive step for evens will be $2n-2$ and $2n$ and by adding them, right? $\endgroup$ – doniyor Nov 25 '12 at 4:48
  • 1
    $\begingroup$ 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. $\endgroup$ – Namaste Nov 25 '12 at 17:23

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.
  • $\begingroup$ but 2n+1 is an odd number, shouldnot be the step 3, 2n+2 ? $\endgroup$ – doniyor Nov 25 '12 at 5:27
  • $\begingroup$ 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} $ ? $\endgroup$ – doniyor Nov 25 '12 at 5:54
  • $\begingroup$ i am pulling out my hair, can you please explain your logic? $\endgroup$ – doniyor Nov 25 '12 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.