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 ;)

## Comments

Sort by:

TopNewestNice note, @Aditya Raut. :D – Sharky Kesa · 2 years, 2 months ago

Log in to reply

\(\bullet \quad \quad\) Challenge to @Sharky Kesa and @Finn Hulse get without Google translate.... – Aditya Raut · 2 years, 2 months ago

Log in to reply

Sarv thumachaach aabhovadhee aahai.

Why did I get 3 down votes for that comment? – Sharky Kesa · 2 years, 2 months ago

Log in to reply

– Aditya Raut · 2 years, 2 months ago

idk, I had upvoted it... I know , one of them has GOT to be Dinesh, he always downvotes my comments and comments that praise me..... And never upvotes my solutions, and if at all in some question the number of upvotes my solution got is more than his, then I don't know how, even his un-elegant solution gets 4-5 upvotes in 3-4 minutes..... strange phenomenaLog in to reply

– Anuj Shikarkhane · 2 years, 2 months ago

But how do you know he always down votes your comments?Log in to reply

– Aditya Raut · 2 years, 2 months ago

We're classmates, so sometimes we open accounts at one person's place, with some other friends too, and I have seen his downvotes when we were in his account.... Also, he can delete the activity, but if you see that in time, then in activity also you can find, I have experienced that. He also made another account "akhilesh bais" for the more number of downvotes, and commenting spam.... I reported it to brilliant, and no one has access to that account now...Log in to reply

for it.– Arya Samanta · 2 years, 2 months agoLog in to reply

– Yuxuan Seah · 2 years, 2 months ago

Actually, I'm quite sure the reason the Brilliant staff made the upvotes was for other, more 'noob' users to see which solutions are the best and most reliable for them to learn from their mistakes. Also, the more upvotes a user has, then (generally) then user has better and more detailed and reliable solutions.Log in to reply

– Arya Samanta · 2 years, 2 months ago

Ya you're right on that part with me..but i was not talking bout them...I am talking 'bout those crazy for upvotes in every solutions okay or not-okay... also in the same way downvotes, if properly stated help us to know what he didn't like in us...but for those who are just crazy to downvote people to pull their leg and make FUN...are...Log in to reply

– Sharky Kesa · 2 years, 2 months ago

This is completely random but do you want to play FTW! on AoPS? :DLog in to reply

Arya

:)– Arya Samanta · 2 years, 2 months agoLog in to reply

I know Hindi because I am Indian. This name is an Internet pseudonym. :D – Sharky Kesa · 2 years, 2 months ago

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

– Sourabh Nolkha · 2 years, 2 months ago

Hahaha.....nice conversationLog in to reply

@Sharky Kesa .... Seriously \(\color{Red}{\bigoplus \Box }\) – Aditya Raut · 2 years, 2 months ago

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

– Anuj Shikarkhane · 2 years, 2 months ago

WHY???Log in to reply

I can read Hindi/Marathi, nextI am indian, and nowI am girl, I have company etc..... too much of surprises :P – Aditya Raut · 2 years, 2 months agoLog 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. – Sharky Kesa · 2 years, 2 months agoLog in to reply

– Anuj Shikarkhane · 2 years, 2 months ago

Hahaha!!!Log in to reply

– Anuj Shikarkhane · 2 years, 2 months ago

Some people down vote just for fun.Log in to reply

– Aditya Raut · 2 years, 2 months ago

And btw, you may use google translate now :PLog in to reply

– Sharky Kesa · 2 years, 2 months ago

'Yours is a blessing to all.' is the translation.Log in to reply

– Finn Hulse · 2 years, 2 months ago

Wait we both speak and read Hindi though.Log in to reply

– Finn Hulse · 2 years, 2 months ago

Oh shoot. Never mind, I don't speak Marathi.Log in to reply

@Aditya Raut, 'Tu te marathit kasa lihila?' Lol! – Ameya Salankar · 2 years, 2 months ago

Log in to reply

Baraha's website . Hope that helps. @Ameya Salankar – Aditya Raut · 2 years, 2 months ago

Log in to reply

@Aditya Raut – Ameya Salankar · 2 years, 1 month ago

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

– Aditya Raut · 2 years, 1 month ago

\(\textbf{adityaraut34@gmail.com}\) ;)Log in to reply

Excellent! – Shraman Das · 2 years, 2 months ago

Log in to reply

You just had completed a first class Numerical Method course – Keshav Sharma · 2 years, 1 month ago

Log in to reply

– Aditya Raut · 2 years, 1 month ago

Didn't get you, sorry ?Log in to reply

– Keshav Sharma · 2 years, 1 month ago

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

@a d Nice note, :) :D ^^ @Aditya Raut u're the best!! – Aswad H. Mangalaeng · 2 years, 2 months ago

Log in to reply

– Aditya Raut · 2 years, 2 months ago

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...... :) – Saikrishna Jampuram · 2 years, 2 months ago

Log in to reply

furthersequence, but that point is correct though.... @Saikrishna Jampuram – Aditya Raut · 2 years, 2 months agoLog in to reply

– Anuj Shikarkhane · 2 years, 2 months ago

Can you explain what are you trying to tell.Log in to reply

– Saikrishna Jampuram · 2 years, 2 months ago

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

– Anuj Shikarkhane · 2 years, 2 months ago

Oh! So you were talking about that.Log in to reply

Not Surprised, Because I have known it. Source: "Art of Problem Solving" by Authur – Sereysopea Ung · 2 years, 2 months ago

Log in to reply

– Aditya Raut · 2 years, 2 months ago

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