<s>[INST] Prove by induction that $9^{n+1}+2^{6n+1}$ is divisible by 11 I need to prove that $9^{n+1}+2^{6n+1} $ is divisible by $11$ $\forall n\in N$ 
Steps I did:

*

*basis step
$$\\ P(0)\ 11\mid(9+2 ) \ (True)$$

*inductive step
$$\\ P(n)\implies P(n+1) \ where: \\  P(n): 9^{n+1}+2^{6n+1} = 11k\\P(n+1): 9^{n+2}+2^{6n+7} = 11k$$
so $$9^{n+2}+2^{6n+7}=11k\\9^n\times9^2+2^{6n}\times2^7=11k$$
Then I don't know how to proceed

 [/INST] Hypothesis gives that if $9^{n+1} \equiv r \pmod{11}$ then $2^{6n+1} \equiv -r \pmod {11}$
The induction step follows:
$$\begin{align}P(n+1) &=9^{n+2}+2^{6n+7} \\
&= 9\cdot 9^{n+1}+2^6\cdot2^{6n+1} \\
&\equiv 9 r + 2^6(-r) \\
&= - 55r \\
&\equiv 0 \pmod{11}\end{align}$$
</s>