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 \[\color{Purple}{(1+\sqrt{5})^n + (1-\sqrt{5})^n}\] is always an even integer, \(\forall n\in \mathbb{N}\), then what can we use ?

\(\mathbf{1.}\quad\)First is, you can use the binomial expansion formula, that is \(\displaystyle \color{Green}{ (1+x)^n = 1+\binom{n}{1} x + \binom{n}{2}x^2+...+\binom{n}{n}x^n = \sum_{k=0}^n \dbinom{n}{k} x^k }\)

Then, because in 2nd term, \(\sqrt{5}\) has a negative sign, in the sum of two brackets' expansion, the terms with an **odd power** of \(\sqrt{5}\) get cancelled and the terms with even power are added to each other twice (Once from \((1+\sqrt{5})^n\) and once from \((1-\sqrt{5})^n\) )

Hence it will be even integer.

\(\mathbf{2.} \quad\)Other way is induction. For \(n=1\), it's trivially true.

Assume for \(n=k\) and prove for \(n=k+1\).

\(\mathbf{3.} \quad\quad\) But the more interesting (seemingly interesting) one, which I thought of is as follows.

See that \(1+\sqrt{5}\) and \(1-\sqrt{5}\) are the roots of the quadratic equation \[x^2- 2x -4=0\]

Thus think of the recurrence relation which has it's characteristic equation \(x^2=2x+4\), and it is \[a_n=2a_{n-1} + 4a_{n-2}\] and with initial conditions, \(a_0=a_1=2\) (We chose these conditions so that we can later get general form as wanted)

Then we see that as the recurrence is starting with \(\textbf{integers}\), and recurrence has integer coefficients , every term will be \(\textbf{integers}\), and from the RHS, as it is \(2(a_{n-1}+2a_{n-2})\), it will always be even.

Now let's generalize the recurrence, and surely, because we designed the recurrence from quadratic whose roots were the \(1+\sqrt{5}\) and \(1-\sqrt{5}\)), and we chose the initial conditions accordingly, so the general term of this recurrence is **confirmly**

\(a_n=(1+\sqrt{5})^n+(1-\sqrt{5})^n\)

And hence, because each term of this recurrence is \(\color{Red}{\textbf{even integer}}\), we have proved that \((1+\sqrt{5})^n+(1-\sqrt{5})^n\) is an even integer \(\forall n\in \mathbb{N}\).

\(\color{Blue}{\textbf{Cool, isn't it?}}\)

And the advantage of this method is that this also proves that actually \((1+\sqrt{5})^n+(1-\sqrt{5})^n\) is always divisible by \(4\), which was not asked though, but an even more precise answer.

\(\color{Blue}{\textbf{Really, there's more than meets the eye in Maths....}}\)

If you never saw this approach before, and liked it then , like (brilliantwise :P) and reshare ;)

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

TopNewestNice note, @Aditya Raut. :D

Log in to reply

Thanks, सर्व तुमचाच आशीर्वाद आहे .

\(\bullet \quad \quad\) Challenge to @Sharky Kesa and @Finn Hulse get without Google translate....

Log in to reply

I don't know Marathi. I used to, but that was long long time ago, when I was only 3. I can pronounce what you have written, however.

Sarv thumachaach aabhovadhee aahai.

Why did I get 3 down votes for that comment?

Log in to reply

Log in to reply

Log in to reply

Log in to reply

for it.Log in to reply

Log in to reply

Log in to reply

Log in to reply

Arya

:)Log in to reply

I know Hindi because I am Indian. This name is an Internet pseudonym. :D

Log in to reply

@Sharky Kesa Sharky Sharky Sharky ! How many surprises am I going to receive from you before I go mad ?

m

Log in to reply

don'tinclude:I work for the CIA

I made my own business which owns every single other corporation on the planet

I am a girl

Log in to reply

Log in to reply

@Sharky Kesa .... Seriously \(\color{Red}{\bigoplus \Box }\)

I really want to go to Jungle after reading the further surprises byLog in to reply

Log in to reply

I can read Hindi/Marathi, nextI am indian, and nowI am girl, I have company etc..... too much of surprises :PLog in to reply

usedto be able to understand Marathi. I can pronounce Hindi characters. And I sad that the list was about what I am not.Log in to reply

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Wait we both speak and read Hindi though.

Log in to reply

Log in to reply

@Aditya Raut, 'Tu te marathit kasa lihila?' Lol!

Log in to reply

Baraha's website . Hope that helps. @Ameya Salankar

Log in to reply

@Aditya Raut

वा! वा! मला तर हे माहितिच न्व्ह्त। Just Great!Log in to reply

Log in to reply

Excellent!

Log in to reply

You just had completed a first class Numerical Method course

Log in to reply

Didn't get you, sorry ?

Log in to reply

you can learn more methods just like this in Numerical Methods.Just google Numerical Methods

Log in to reply

@a d Nice note, :) :D ^^ @Aditya Raut u're the best!!

Log in to reply

Pleased to hear that, \(\color{Red}{\Huge{\textbf{Thank you very much!}}}\)

Log in to reply

For n=1. Answer is 2. Which is not divisible by 4..... I think it's divisible by 4 right from n=2...... :)

Log in to reply

Ok, that's good observation, but i didn't mean for them. See the approach I have told asks initial conditions which we got by n=0 and n=1 , and all else is talked about

furthersequence, but that point is correct though.... @Saikrishna JampuramLog in to reply

Can you explain what are you trying to tell.

Log in to reply

Before the last few lines from the explanation he is telling that term is always divisible by 4 ..... So if you substitute n=1 and check it..... It's not. :)

Log in to reply

Log in to reply

Not Surprised, Because I have known it. Source: "Art of Problem Solving" by Authur

Log in to reply

Oh where? Please give the source, I didn't know it's already used somewhere. Thanks for sharing though ...

Log in to reply