Prove that $13^n -4^n$ is divisible by $9$ for every integer $\geq $ Prove that $13^n - 4^n$ is divisible by $9$ for every integer $n$ is greater than or equal to $1$. 


I have written down my answer but I don't know if it is correct.

$    13(13^k) - 4^{(k+1)}$
$=    9(13^k) + 4(13^k) - 4{(4^k)}$
$=    9(13^k) + 4(13^k - 4^k)$
$=    9(13^k) + 4(9a)$ where $9a = 13^k -4^k$
$=    9(13^k + 4a)$
$=    9b$ where $b=13^k + 4a$
Just use $a^n -b^n=(a-b)(a^{n-1} + ... + b^{n-1})$

Another way is using induction by n as you did it (more or less) in the OP.
Take base case $ n=1$, $9$ is divisible by $9$. Assume it to be true for $ n&gt;=1$, then replace $n$ by $n+1$.

$13.13^n -4.4^n $ can be written as $9.13^n \,  + 4.(13^n-4^n)$ and both parts of it are divisible by 9.