Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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
add comment

2 Answers

up vote 6 down vote accepted

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.


share|improve this answer
    
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
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. –  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.
share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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