Prove a number is divisible by 2^{2008}

[anemone]

Prove that the number $1+\left\lfloor{}\right(\sqrt{17}+5)^{2008} \rfloor$ is divisible by $2^{2008}$.

 

[kaliprasad]

Spoiler

we have
$(\sqrt{17}+5)^{2008}+ (5-\sqrt{17})^{2008}$
is integer and $(5-\sqrt{17}) $ is less than 1 so
given expression is

$(\sqrt{17}+5)^{2008}+ (5-\sqrt{17})^{2008}$

if we get x = $(5+\sqrt{17}) $
as $(5+\sqrt{17})(5-\sqrt{17}) = 8$

then given expression is
$(x)^{2008} + (\frac{8}{x})^{2008}$

we have $x + \frac{8}{x}=10$

we shall now show it by induction that
$x^{n} + (\frac{8}{x})^{n}$
is divisible by $2^{n}$

for n =1 it is true as it is 10

for n =2

it is $x^{2}+(\frac{8}{x})^2 =(x+(\frac{8}{x}))^2-2 * 8 = 10^2 - 16 = 84 $ divisible by 4

for n = 3

it is $x^{3}+(\frac{8}{x})^3 =(x+(\frac{8}{x}))^3-3 * 8 * (x + \frac{8}{x}) = 10^3- 3 *8 * 10 = 760 $ divisible by 8

so it is true for n = 1,2, 3

not we go for induction step
$(x^{n}+(\frac{8}{x})^n)(x+\frac{8}{x})= (x^{n+1} + (\frac{8}{x})^{n+1}) + 8(x^{n-1} + (\frac{8}{x})^{n-1}) $

hence
$x^{n+1}+(\frac{8}{x})^{n+1}= (x+\frac{8}{x})(x^{n} + (\frac{8}{x})^{n}) - 8(x^{n-1} + (\frac{8}{x})^{n-1}) $

or $x^{n+1}+(\frac{8}{x})^{n+1}= (x+\frac{8}{x})(x^{n} + (\frac{8}{x})^{n}) -2^3(x^{n-1} + (\frac{8}{x})^{n-1}) $

now if $x^{n}+(\frac{8}{x})^{n}$ is divsible by $2^n$

then it is easy to see that 1st term of RHS is disvisible by $2^{n+1}$ and 2nd by $2^{n+2}$ and hence LHS is divsible by $2^{n+1}$

so induction step is proved and hence given expression is divisible by $2^{2008}$

 

[Opalg]

My solution is similar to kaliprasad's.

[sp]Let $\alpha = 5 + \sqrt{17}$, $\beta = 5 - \sqrt{17}$. Then $\alpha + \beta = 10$, $\alpha\beta = 8$, and so $\alpha$ and $\beta$ are the roots of the equation $x^2 - 10x + 8 = 0.$ Then $x^{n+2} - 10x^{n+1} + 8x^n = 0$ (for all $n\geqslant0$).

Let $S_n = \alpha^n + \beta^n$. Then $\alpha^{n+2} - 10\alpha^{n+1} + 8\alpha^n = 0$ and $\beta^{n+2} - 10\beta^{n+1} + 8\beta^n = 0$, so by addition $S_{n+2} - 10S_{n+1} + 8S_n = 0$. It follows by an easy induction argument that $S_n$ is an integer. Since $0<\beta^n < 1$ it then follows that $S_n = \lfloor\alpha^n \rfloor + 1.$

It remains to prove by induction that $S_n$ is a multiple of $2^n$, say $S_n = 2^nT_n$ for some integer $T_n$. Since $S_0 = 2$ and $S_1= 10$, this holds for $n=0$ and $n=1$. Assume that the result is true for $n$ and $n+1$. Then $S_{n+2} = 10S_{n+1} - 8S_n = 10(2^{n+1}T_{n+1}) - 8(2^nT_n) = 2^{n+2}(5T_{n+1} - 2T_n),$ which is a multiple of $2^{n+2}$ as required.[/sp]