Waste less time on Facebook — follow Brilliant.
×

More than meets the eye...

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

Note by Aditya Raut
3 years, 2 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Nice note, @Aditya Raut. :D

Sharky Kesa - 3 years, 2 months ago

Log in to reply

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

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

Aditya Raut - 3 years, 2 months ago

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?

Sharky Kesa - 3 years, 2 months ago

Log in to reply

@Sharky Kesa 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 phenomena

Aditya Raut - 3 years, 2 months ago

Log in to reply

@Aditya Raut But how do you know he always down votes your comments?

Anuj Shikarkhane - 3 years, 2 months ago

Log in to reply

@Anuj Shikarkhane 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...

Aditya Raut - 3 years, 2 months ago

Log in to reply

@Aditya Raut I think, for him(upvotes) do matter....he's just crazy for them...but downvotes do matter for all if one is not crazy for it.

Arya Samanta - 3 years, 2 months ago

Log in to reply

@Arya Samanta 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.

Yuxuan Seah - 3 years, 2 months ago

Log in to reply

@Yuxuan Seah 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...

Arya Samanta - 3 years, 2 months ago

Log in to reply

@Arya Samanta This is completely random but do you want to play FTW! on AoPS? :D

Sharky Kesa - 3 years, 2 months ago

Log in to reply

@Sharky Kesa Ya of course but time matters.... now our school is hosting a inter school extravaganza also..I've to go to a musical BAND HUNT competition this week . ...let us sink in the conversation..Would you give me your email-ID or get mine from my Brilliant account and then............................. if you tell me 'bout ForTheWin(I don't like to read 'bout it on the net) and if I get time i'll love to PLAY. BTW how do you know hindi.?.

Arya :)

Arya Samanta - 3 years, 2 months ago

Log in to reply

@Arya Samanta Well, FTW! is a game on Art of Problem Solving. The website is basically a math forum, sort of like Brilliant. FTW! is a game where you answer math questions as quickly as possible.

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

Sharky Kesa - 3 years, 2 months ago

Log in to reply

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

m

m

Aditya Raut - 3 years, 2 months ago

Log in to reply

@Aditya Raut I have a lot more. Some of them don't include:

  • I work for the CIA

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

  • I am a girl

Sharky Kesa - 3 years, 2 months ago

Log in to reply

@Aditya Raut Hahaha.....nice conversation

Sourabh Nolkha - 3 years, 2 months ago

Log in to reply

@Sourabh Nolkha I really want to go to Jungle after reading the further surprises by @Sharky Kesa .... Seriously \(\color{Red}{\bigoplus \Box }\)

Aditya Raut - 3 years, 2 months ago

Log in to reply

@Aditya Raut WHY???

Anuj Shikarkhane - 3 years, 2 months ago

Log in to reply

@Anuj Shikarkhane First of all, one big was I can read Hindi/Marathi , next I am indian , and now I am girl, I have company etc ..... too much of surprises :P

Aditya Raut - 3 years, 2 months ago

Log in to reply

@Aditya Raut I used to be able to understand Marathi. I can pronounce Hindi characters. And I sad that the list was about what I am not.

Sharky Kesa - 3 years, 2 months ago

Log in to reply

@Aditya Raut Hahaha!!!

Anuj Shikarkhane - 3 years, 2 months ago

Log in to reply

@Sharky Kesa Some people down vote just for fun.

Anuj Shikarkhane - 3 years, 2 months ago

Log in to reply

@Sharky Kesa And btw, you may use google translate now :P

Aditya Raut - 3 years, 2 months ago

Log in to reply

@Aditya Raut 'Yours is a blessing to all.' is the translation.

Sharky Kesa - 3 years, 2 months ago

Log in to reply

Wait we both speak and read Hindi though.

Finn Hulse - 3 years, 2 months ago

Log in to reply

@Finn Hulse Oh shoot. Never mind, I don't speak Marathi.

Finn Hulse - 3 years, 2 months ago

Log in to reply

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

Ameya Salankar - 3 years, 2 months ago

Log in to reply

@Ameya Salankar माझ्या नागपूरच्या मित्रा , मी बराहा पॅड नावाचं सॉफ्ट्वेअर वापरलं.

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

Aditya Raut - 3 years, 2 months ago

Log in to reply

@Aditya Raut वा! वा! मला तर हे माहितिच न्व्ह्त। Just Great! @Aditya Raut

Ameya Salankar - 3 years, 1 month ago

Log in to reply

@Ameya Salankar \(\textbf{adityaraut34@gmail.com}\) ;)

Aditya Raut - 3 years, 1 month ago

Log in to reply

Excellent!

Shraman Das - 3 years, 2 months ago

Log in to reply

You just had completed a first class Numerical Method course

Keshav Sharma - 3 years, 1 month ago

Log in to reply

Didn't get you, sorry ?

Aditya Raut - 3 years, 1 month ago

Log in to reply

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

Keshav Sharma - 3 years, 1 month ago

Log in to reply

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

Aswad H. Mangalaeng - 3 years, 1 month ago

Log in to reply

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

Aditya Raut - 3 years, 1 month ago

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 - 3 years, 2 months ago

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 further sequence, but that point is correct though.... @Saikrishna Jampuram

Aditya Raut - 3 years, 2 months ago

Log in to reply

Can you explain what are you trying to tell.

Anuj Shikarkhane - 3 years, 2 months ago

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. :)

Saikrishna Jampuram - 3 years, 2 months ago

Log in to reply

@Saikrishna Jampuram Oh! So you were talking about that.

Anuj Shikarkhane - 3 years, 2 months ago

Log in to reply

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

Sereysopea Ung - 3 years, 1 month ago

Log in to reply

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

Aditya Raut - 3 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...