3
$\begingroup$

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
    i know, it was also my question, but i didnot get any answer, thats why i am posting it again.2012-11-24
  • 1
    **Don't do that**. [This is what you do](http://math.stackexchange.com/faq#bounty) if you don't get an answer.2012-11-26
  • 0
    okay, thanks :D2012-11-28

2 Answers 2

7

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.


  • 0
    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)?2012-11-24
  • 0
    Sorry to see it late, wow, very nicely explained! i didnot know that good-to-know things2012-11-25
  • 0
    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?2012-11-25
  • 0
    no, the inductive step for evens will be $2n-2$ and $2n$ and by adding them, right?2012-11-25
  • 0
    i find this really confusing, and identities of fibonacci are little consufing, the calculation of Dedalus on fibonacci's is still confusing me.2012-11-25
  • 1
    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.2012-11-25
  • 0
    yeah i will get back to this in a second, i couldnot solve the problem by now..2012-11-25
1

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.
  • 0
    but 2n+1 is an odd number, shouldnot be the step 3, 2n+2 ?2012-11-25
  • 0
    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} $ ?2012-11-25
  • 0
    i am pulling out my hair, can you please explain your logic?2012-11-25