# 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{#69047E}{(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{#20A900}{ (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{#D61F06}{\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{#3D99F6}{\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{#3D99F6}{\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 ;)

5 years, 9 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

- 5 years, 9 months ago

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

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

- 5 years, 9 months ago

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.

Why did I get 3 down votes for that comment?

- 5 years, 9 months ago

Some people down vote just for fun.

- 5 years, 9 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 phenomena

- 5 years, 9 months ago

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.

- 5 years, 9 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.

- 5 years, 9 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...

- 5 years, 9 months ago

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

- 5 years, 9 months ago

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

- 5 years, 9 months ago

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

- 5 years, 9 months ago

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

m

- 5 years, 9 months ago

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

- 5 years, 9 months ago

Hahaha.....nice conversation

- 5 years, 9 months ago

I really want to go to Jungle after reading the further surprises by @Sharky Kesa .... Seriously $\color{#D61F06}{\bigoplus \Box }$

- 5 years, 9 months ago

WHY???

- 5 years, 9 months ago

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

- 5 years, 9 months ago

Hahaha!!!

- 5 years, 9 months ago

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.

- 5 years, 9 months ago

- 5 years, 9 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...

- 5 years, 9 months ago

And btw, you may use google translate now :P

- 5 years, 9 months ago

'Yours is a blessing to all.' is the translation.

- 5 years, 9 months ago

Wait we both speak and read Hindi though.

- 5 years, 9 months ago

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

- 5 years, 9 months ago

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

- 5 years, 9 months ago

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

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

- 5 years, 9 months ago

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

- 5 years, 8 months ago

$\textbf{adityaraut34@gmail.com}$ ;)

- 5 years, 8 months ago

Excellent!

- 5 years, 9 months ago

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

- 5 years, 9 months ago

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

- 5 years, 9 months ago

Can you explain what are you trying to tell.

- 5 years, 9 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. :)

- 5 years, 9 months ago

Oh! So you were talking about that.

- 5 years, 9 months ago

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

- 5 years, 9 months ago

Pleased to hear that, $\color{#D61F06}{\Huge{\textbf{Thank you very much!}}}$

- 5 years, 9 months ago

You just had completed a first class Numerical Method course

- 5 years, 8 months ago

Didn't get you, sorry ?

- 5 years, 8 months ago

- 5 years, 8 months ago

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

- 5 years, 9 months ago

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

- 5 years, 9 months ago