MHB Prove a number is divisible by 2^{2008}

  • Thread starter Thread starter anemone
  • Start date Start date
AI Thread Summary
The number \(1+\left\lfloor(\sqrt{17}+5)^{2008}\right\rfloor\) is shown to be divisible by \(2^{2008}\) through a recursive relationship involving the roots \(\alpha = 5 + \sqrt{17}\) and \(\beta = 5 - \sqrt{17}\). The sequence \(S_n = \alpha^n + \beta^n\) is established, which satisfies the recurrence relation \(S_{n+2} - 10S_{n+1} + 8S_n = 0\). An induction argument confirms that \(S_n\) is an integer and can be expressed as \(S_n = \lfloor\alpha^n\rfloor + 1\). Further, it is proven that \(S_n\) is a multiple of \(2^n\), leading to the conclusion that \(S_{2008}\) is a multiple of \(2^{2008}\). Thus, the original expression is indeed divisible by \(2^{2008}\).
anemone
Gold Member
MHB
POTW Director
Messages
3,851
Reaction score
115
Prove that the number $1+\left\lfloor{}\right(\sqrt{17}+5)^{2008} \rfloor$ is divisible by $2^{2008}$.
 
Mathematics news on Phys.org
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}$
 
Last edited:
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]
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Thread 'Video on imaginary numbers and some queries'
Hi, I was watching the following video. I found some points confusing. Could you please help me to understand the gaps? Thanks, in advance! Question 1: Around 4:22, the video says the following. So for those mathematicians, negative numbers didn't exist. You could subtract, that is find the difference between two positive quantities, but you couldn't have a negative answer or negative coefficients. Mathematicians were so averse to negative numbers that there was no single quadratic...
Thread 'Unit Circle Double Angle Derivations'
Here I made a terrible mistake of assuming this to be an equilateral triangle and set 2sinx=1 => x=pi/6. Although this did derive the double angle formulas it also led into a terrible mess trying to find all the combinations of sides. I must have been tired and just assumed 6x=180 and 2sinx=1. By that time, I was so mindset that I nearly scolded a person for even saying 90-x. I wonder if this is a case of biased observation that seeks to dis credit me like Jesus of Nazareth since in reality...
Back
Top