Question

Proof the following:
\[
(3+\sqrt{5})^n+(3-\sqrt{5})^n\text{ is divisible by }2^n
\]

Answer 1

do it

Answer 2

Do the binomial expansion and do simple manipulations. You can take 2^n as common.

Answer 3

My attempt on mathematical induction:
\[
\begin{align*}
&\left(3+\sqrt{5}\right)^{k+1}+\left(3-\sqrt{5}\right)^{k+1}
\\
=&\left(3+\sqrt{5}\right)\left(3+\sqrt{5}\right)^{k}+\left(3-\sqrt{5}\right)\left(3-\sqrt{5}\right)^{k}
\\
=&\left(3+\sqrt{5}\right)\sum_{i=0}^{k} \left(\binom{k}{i}3^{k-i}\sqrt{5}^{i}\right)+\left(3-\sqrt{5}\right)\sum_{i=0}^{k} \left(\binom{k}{i}3^{k-i}(-1)^{i}\sqrt{5}^{i}\right)
\\
=&\left(3+\sqrt{5}\right)\left(\sum_{i=0}^{\left\lfloor\frac{k}{2}\right\rfloor } \left(\binom{k}{2i}3^{k-2i}\sqrt{5}^{2i}\right)+\sum_{j=0}^{\left\lfloor\frac{k}{2}\right\rfloor}\left(\binom{k}{2j+1}3^{k-2j-1}\sqrt{5}^{2j+1}\right)\right)
\\
&+\left(3-\sqrt{5}\right)\left(\sum_{u=0}^{\left\lfloor\frac{k}{2}\right\rfloor}\left(\binom{k}{2u}3^{k-2u}\sqrt{5}^{2u}\right)-\sum_{v=0}^{\left\lfloor\frac{k}{2}\right\rfloor}\left(\binom{k}{2v+1}3^{k-2v-1}\sqrt{5}^{2v+1}\right)\right)
\\
=& 6\left(\sum_{i=0}^{\left\lfloor\frac{k}{2}\right\rfloor} \left(\binom{k}{2i}3^{k-2i}\sqrt{5}^{2i}\right)\right)+2\sqrt{5}\left(\sum_{v=0}^{\left\lfloor\frac{k}{2}\right\rfloor}\left(\binom{k}{2v+1}3^{k-2v-1}\sqrt{5}^{2v+1}\right)\right)
\\
=&6\left(\sum_{i=0}^{\left\lfloor\frac{k}{2}\right\rfloor} \left(\binom{k}{2i}3^{k-2i}\sqrt{5}^{2i}\right)\right)+\frac{10}{3}\left(\sum_{v=0}^{\left\lfloor\frac{k}{2}\right\rfloor}\left(\binom{k}{2v+1}3^{k-2v}\sqrt{5}^{2v}\right)\right)
\\
=&\frac{8}{3}\left(\sum_{i=0}^{\left\lfloor\frac{k}{2}\right\rfloor} \left(\binom{k}{2i}3^{k-2i}\sqrt{5}^{2i}\right)\right)+\frac{10}{3}\left(\sum_{i=0}^{\left\lfloor\frac{k}{2}\right\rfloor} \left(\binom{k}{2i}3^{2i}\sqrt{5}^{k-2i}+\binom{k}{2i+1}3^{2i}\sqrt{5}^{k-2i}\right)\right)
\\
=&\frac{8}{3}\left(\sum_{i=0}^{\left\lfloor\frac{k}{2}\right\rfloor} \left(\binom{k}{2i}3^{k-2i}\sqrt{5}^{2i}\right)\right)+\frac{10}{3}\left(\sum_{i=0}^{\left\lfloor\frac{k}{2}\right\rfloor} \left(\binom{k+1}{2i+1}3^{k-2i}\sqrt{5}^{2i}\right)\right)
\end{align*}
\]

And yes, the first term is equal to the last term. I checked with Mathematica lol!

Answer 4

Given this piece of mess binomial expansion is unlikely to work lol!

Answer 5

What values \(n\) can take ?

Answer 6

n in natural number including 0 I think.

Answer 7

I checked and it is for all natural number (does not including 0).

Answer 8

@ganeshie8 *sigh*

Answer 9

This has something to do with the induction proof of binomial theorem, which I don't understand.

Answer 10

ermm binomial them will help
i tried mod but its only work for odd n

so lets try using binomial :)

Answer 11

\[(3+\sqrt{5})^n + (3-\sqrt{5})^n= 3^n (1+\sqrt{5}/3)^n + 3^n (1-\sqrt{5}/3)^n\]
Let's call \(\sqrt{5}/3\) as t.
\[(3+\sqrt{5})^n + (3-\sqrt{5})^n= 3^n \left( (1+t)^n + (1-t)^n \right)\]
So, \[(1+t)^n + (1-t)^n = \sum_{r = 0}^{n} \binom{n}{r} t^r + \sum_{r = 0}^{n} \binom{n}{r} t^r (-1)^r = \sum_{r = 0}^{n} \binom{n}{r} t^r \left(1+(-1)^r\right) \]
This is 0 if r is odd.
So \( (1+t)^n + (1-t)^n =2\sum_{r = 0,2,4}^{n} \binom{n}{r} t^r \)
Now apply mathematical induction.

Answer 12

Ah. If I remember correctly the professor give a hint like this:
\[(x+y)^n=a(x+y)^{n-1}+b(x+y)^{n-2}\]
where a and b is some random thing and THEY ARE NOT CONSTANTS.

Answer 13

i made huge typo with \( \left(\begin{matrix}n \\i\end{matrix}\right) \)
its not constant lol i was focusing on the idea hehe

Answer 14

I am pretty sure if someone could understand this proof of binomial theorem then the proof \(2^n|(3+\sqrt{5})^n+(3-\sqrt{5})\) should come naturally.
https://www.math.hmc.edu/calculus/tutorials/binomial_thm/induction.html

Answer 15

This proof might be better.
http://www.math.ucsd.edu/~benchow/BinomialTheorem.pdf

Answer 16

Do you know mathematical induction ?

Answer 17

ok ok i need to rewrite all what i wrote again xD
but more neat

for n is odd
then
\(2(3) =0 \mod 2 \)
\((3+3\sqrt 5 -\sqrt 5) =0 \mod 2 \)
\((3+\sqrt 5 ) =-(3-\sqrt 5 ) \mod 2 \)

\((3+\sqrt 5 )^n =-(3-\sqrt 5 )^n \mod 2^n \)
\((3+\sqrt 5 )^n +-(3-\sqrt 5 )^n = 0 \mod 2^n \)


nw we need to prove for n is even

Answer 18

Yes but I can't make \((3+\sqrt{5})^{n+1}+(3-\sqrt{5})^{n+1}\) into something related to \((3+\sqrt{5})^{n}+(3-\sqrt{5})^{n}\).

\((1+t)^n + (1-t)^n =2\sum_{r = 0,2,4}^{n} \binom{n}{r} t^r\) <-- This looks promising but I don't know how to make it to n+1.

I have to go get my dinner so please let me have a break. I feel drained... :(

Answer 19

wait good idea we proved it for n when its odd so wanna see for n+1

Answer 20

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


\((3+\sqrt 5 )^n =-(3-\sqrt 5 )^n \mod 2^n\) is true (proved before for n odd )
so we need to show
\((3+\sqrt 5 )^{n+1} =-(3-\sqrt 5 )^{n+1} \mod 2^{n+1}\)

its enough to show

\( (3+\sqrt 5 ) = (3-\sqrt 5 ) \mod 2 \)

Answer 21

Something is seriously wrong. How can \((3+\sqrt 5 ) = (3-\sqrt 5 ) \mod 2\)?

Answer 22

ik , me too still confused about it

Answer 23

ok ok one more try :P
lets assume n is even

\((3+\sqrt 5)^n=\)
\(\left(\begin{matrix}n \\ 0\end{matrix}\right) 3^n+ \left(\begin{matrix}n \\ 1\end{matrix}\right) 3^{n-1} \sqrt 5 +\left(\begin{matrix}n \\ 2\end{matrix}\right) 3^{n-2} \sqrt 5^2 +\left(\begin{matrix}n \\ 3\end{matrix}\right) 3^{n-3} \sqrt 5^3 + . . . +\left(\begin{matrix}n \\ n\end{matrix}\right) \sqrt 5^n \)

\((3-\sqrt 5)^n=\)
\(\left(\begin{matrix}n \\ 0\end{matrix}\right) 3^n- \left(\begin{matrix}n \\ 1\end{matrix}\right) 3^{n-1} \sqrt 5 +\left(\begin{matrix}n \\ 2\end{matrix}\right) 3^{n-2} \sqrt 5^2 -\left(\begin{matrix}n \\ 3\end{matrix}\right) 3^{n-3} \sqrt 5^3 + . . . +\left(\begin{matrix}n \\ n\end{matrix}\right) \sqrt 5^n \)

Answer 24

\((3+\sqrt 5)^n+(3-\sqrt 5)^n=\)
\(\left(\begin{matrix}n \\ 0\end{matrix}\right) 3^n+ 2 [\left(\begin{matrix}n \\ 2\end{matrix}\right) 3^{n-2} \sqrt 5^2 +....... ]+\left(\begin{matrix}n \\ n\end{matrix}\right) \sqrt 5^n \)


mmm its 2 not 2^n xD


*give up * :P
i have no other way only induction in that link work

Answer 25

I checked with Mathematica that this is correct.
\[\frac{8}{3}\left(\sum_{i=0}^{\left\lfloor\frac{k}{2}\right\rfloor} \left(\binom{k}{2i}3^{k-2i}\sqrt{5}^{2i}\right)\right)+\frac{10}{3}\left(\sum_{i=0}^{\left\lfloor\frac{k}{2}\right\rfloor} \left(\binom{k+1}{2i+1}3^{k-2i}\sqrt{5}^{2i}\right)\right)\]
Now split it into even and odd case.

Even case:
\[k=2m\]
Odd case:
\[k=2m+1\]
What am I suppose to do with the index of summation?

Answer 26

@ikram002p your proof using mods and binomial theorem works nicely, don't give up - you're 2-3 steps away from the complete neat solution

Answer 27

see if you can use below :
\[\binom{n}{0} + \binom{n}{1} + \cdots \binom{n}{n} = 2^n\]

Answer 28

and notice that \(3 \equiv 5 \equiv 1 \mod 2\)

Answer 29

idk , i cant think of anything to complete it

Answer 30

but xD
show me lol xD

Answer 31

yeah that was bit greedy ! doesn't work >.<

Answer 32

huh

Answer 33

mod does not work

Answer 34

note that

Answer 35

\[
\text{Let }x\text{ be }\left(3+\sqrt{5}\right).\\
\text{Let }y\text{ be }\left(3-\sqrt{5}\right).\\

\text{Note that }x^n+y^n=(x+y)\left(x^{n-1}+y^{n-1}\right)-(xy)\left(x^{n-2}+y^{n-2}\right)\\
\text{Assume }2^n|\left(3+\sqrt{5}\right)^n+\left(3-\sqrt{5}\right)^n\text{ holds for all }n<k\text{.}\\
\begin{align*}
x^k+y^k&=(x+y)\left(x^{k-1}+y^{k-1}\right)-(xy)\left(x^{k-2}+y^{k-2}\right)\\
&=6\left(u\,2^{k-1}\right)+4\left(v\,2^{k-2}\right)\\
&=3u\,2^k+v\,2^k\\
&=2^k(3u+v)\\
\text{I deserve a Q.E.D.}
\end{align*}
\]

Answer 36

Looks nice!

Answer 37

But you have to assume the statement true for for n = k-1 and k-2, \(k\ge 3\). And for that you should have the statement true for both n= 1 and n=2.

Answer 38

Ah yes, I have completely forgotten the base case part. Not bad for my first strong induction proof.