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

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 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"

Math

Appears 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}

Easy Math Editor

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.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

Nice note, @Aditya Raut. :D

Sharky Kesa - 6 years, 10 months ago

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

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

Aditya Raut - 6 years, 10 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.

Sarv thumachaach aabhovadhee aahai.

Why did I get 3 down votes for that comment?

@Sharky Kesa – Some people down vote just for fun.

Anuj Shikarkhane - 6 years, 10 months ago

@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 – 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 - 6 years, 10 months ago

@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 - 6 years, 10 months ago

@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 – This is completely random but do you want to play FTW! on AoPS? :D

@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 – 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 – @Sharky Kesa Sharky Sharky Sharky ! How many surprises am I going to receive from you before I go mad ?

@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

@Aditya Raut – Hahaha.....nice conversation

Sourabh Nolkha - 6 years, 10 months ago

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

Aditya Raut - 6 years, 9 months ago

@Aditya Raut – WHY???

Anuj Shikarkhane - 6 years, 9 months ago

@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 – Hahaha!!!

@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 - 6 years, 9 months ago

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

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

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

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

Wait we both speak and read Hindi though.

Finn Hulse - 6 years, 10 months ago

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

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

Ameya Salankar - 6 years, 9 months ago

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

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

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

@Ameya Salankar – $\textbf{[email protected]}$ ;)

Excellent!

Shraman Das - 6 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...... :)

Saikrishna Jampuram - 6 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

Can you explain what are you trying to tell.

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 – Oh! So you were talking about that.

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

Aswad Hariri Mangalaeng - 6 years, 9 months ago

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

You just had completed a first class Numerical Method course

Keshav Sharma - 6 years, 9 months ago

Didn't get you, sorry ?

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

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

Sereysopea Ung - 6 years, 9 months ago

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

Math	Appears 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}$