Well, this is about an innovative approach (innovative in the sense, I didn't see it anywhere before), to solve some induction problems using the recurrence relations.
We know that if you want to prove that is always an even integer, , then what can we use ?
First is, you can use the binomial expansion formula, that is
Then, because in 2nd term, has a negative sign, in the sum of two brackets' expansion, the terms with an odd power of get cancelled and the terms with even power are added to each other twice (Once from and once from )
Hence it will be even integer.
Other way is induction. For , it's trivially true.
Assume for and prove for .
But the more interesting (seemingly interesting) one, which I thought of is as follows.
See that and are the roots of the quadratic equation
Thus think of the recurrence relation which has it's characteristic equation , and it is and with initial conditions, (We chose these conditions so that we can later get general form as wanted)
Then we see that as the recurrence is starting with , and recurrence has integer coefficients , every term will be , and from the RHS, as it is , it will always be even.
Now let's generalize the recurrence, and surely, because we designed the recurrence from quadratic whose roots were the and ), and we chose the initial conditions accordingly, so the general term of this recurrence is confirmly
And hence, because each term of this recurrence is , we have proved that is an even integer .
And the advantage of this method is that this also proves that actually is always divisible by , which was not asked though, but an even more precise answer.
If you never saw this approach before, and liked it then , like (brilliantwise :P) and reshare ;)