Proof by induction

[swagmaster420x]

Prove (3 + sqrt(5))^n + (3 - sqrt(5))^n is divisible by 2^n for all positive integers n.

[josh93248]

Uh... What is the point of this?

[toryka]

What is this? Looks so scary to me 

[swagmaster420x]

Lol learn math noobs w t f

[ted]

x^n+y^n=(x+y){x^(n-1)+y^(n-1)}-xy{x^(n-2)+y^(n-2)}

Substitute 3+sqrt5 for x and 3-sqrt5 for y, assume it is true for the first two n, and the result follows because x+y=6 and xy=4.

[swagmaster420x]

x^n+y^n=(x+y){x^(n-1)+y^(n-1)}-xy{x^(n-2)+y^(n-2)}

Substitute 3+sqrt5 for x and 3-sqrt5 for y, assume it is true for the first two n, and the result follows because x+y=6 and xy=4.

Clever , bravo !
Is that expansion something you just knew, or played around with to get?
Another solution which results in the same form is observing that 3 +- sqrt5 are the roots of
x^2 - 6x + 4.

[ted]

Is that expansion something you just knew, or played around with to get?

I don't know, just a guess really, although it is a standard technique to express a symmetric function in terms of the elementary symmetric functions. I might have remembered that from fifty years ago I suppose !