Exponential Divisibility


$f(n) = 10^n - (5 + \sqrt{17})^n - (5 - \sqrt{17})^n$ is a function which is valid for all integers $n$ greater than $1$. Prove that, $f(n)$ is always perfectly divisible by $2^{n+1}$.


Source: BdMO 2024 National Junior P8


Proof Based Problems  


  0 Upvote                    2 Downvote


Solution

Disclaimer: The solutions we've shared are just one exciting approach, and there are surely many other wonderful methods out there. We’d love to hear your alternative solutions in the community thread below, so let's keep the creativity flowing!

$(5+\sqrt{17})$ and $5-\sqrt{17}$ are the roots of the equation

\[0=x^2-x(5+\sqrt{17}+5-\sqrt{17})+(5+\sqrt{17})(5-\sqrt{17})=x^2-10x+8\]

So, they both satisfy the equation

$x^2-10x+8=0\implies x^n=10x^{n-1}-8x^{n-2}$

Let $(5+\sqrt{17})^n+(5-\sqrt{17})^n=a_n$

    $$(5+\sqrt{17})^n=10(5+\sqrt{17})^{n-1}-8(5+\sqrt{17})^{n-2}$$

$$ (5-\sqrt{17})^n=10(5-\sqrt{17})^{n-1}-8(5-\sqrt{17})^{n-2}$$

$$a_n=10a_{n-1}-8a_{n-2}$$


Claim: $v_2(a_n)=n$.

Proof:  We will prove using induction.

Base case: 

$a_1=(5+\sqrt{17})+(5-\sqrt{17})=10=2\cdot 5$

$a_2=(5+\sqrt{17})^2+(5-\sqrt{17})^2=2^2\cdot 21$


Inductive step:

Given that $v_2(a_{n-1})=n-1$ and $v_2(a_{n-2})=n-2$, we will prove that $v_2(a_n)=n$.

Let $a_{n-1}=2^{n-1}p$ and $a_{n-2}=2^{n-2}q$

\[a_n=10a_{n-1}-8a_{n-2}=5\cdot2^np-2^{n+1}q\]

$v_2(5\cdot2^np)\neq v_2(2^{n+1}q)\implies v_2(a_n)=\min(v_2(5\cdot2^np), v_2(2^{n+1}q))=\min(n,n+1)=n$.


Now, we need to prove $2^{n+1}$ divides $10^n+(5+\sqrt{17})^n+(5-\sqrt{17})^n=10^n+a_n$

But, $v_2(10^n)=v_2(2^n\cdot5^n)=n$. So, $v_2(a_n)=v_2(10^n)$

So, $v_2(10^n+a_n)>v_2(10^n)=n$

So, $v_2(10^n+(5+\sqrt{17})^n+(5-\sqrt{17})^n)\geq n+1$

So, $2^{n+1}$ divides $10^n+(5+\sqrt{17})^n+(5-\sqrt{17})^n$

This is a proof based problem added for learning purposes and does not accept submissions.

You can view the solution by clicking on the solution tab.

Editorial



Need a hint? Checkout the editorial.

View Editorial