How to prove that $3^{3n+2}+2^{4n+1}$ is a multiple of 11 How can I prove that following is a multiple of 11 with the induction method?
 $$3^{3n+2}+2^{4n+1}$$ 
 A: Compute modulo 11 $$3^{3n+2}+2^{4n+1} \equiv 9\times 27^n + 2\times 16^n \equiv
9\times 5^n+2\times 5^n \equiv 11\times 5^n \equiv 0  \pmod {11}$$ 
A: Using induction:
Test for base case $n=0$:
$$3^2+2^1=11$$
$11$ is a multiple of $11$. Hence, true for $n=0$.

Inductive step: Assume true for $n=k$:
$$\frac{3^{3k+2}+2^{4k+1}}{11}=p$$
Where $p \in \mathbb{N}$.
$$3^{3k+2}+2^{4k+1}=11p \tag{1}$$
For $n=k+1$:
$$3^{3k+5}+2^{4k+5}\tag{2}$$
Now, we will try to put $(2)$ in terms of $p$ using equation $(1)$.
$$27\cdot 3^{3k+2}+16\cdot 2^{4k+1}=\color{blue}{16\cdot 3^{3k+2}}+11\cdot 3^{3k+2}+\color{blue}{16\cdot 2^{4k+1}}$$
The $\color{blue}{\text{blue}}$ text can be put in terms of $p$:
$$\color{blue}{16\cdot 11p}+11\cdot 3^{3k+2}$$
Now, note that each of these terms is divisible by $11$, since $k\in \mathbb{N}$ and $p\in \mathbb{N}$.
Therefore $n=k+1$ follows from $n=k$. Thus, the statement is true for all $n\in \mathbb{N}$.
If you have any doubts or questions, please do not hesitate to ask.
A: Base case, $n=0$: $\quad 3^{0+2}+2^{0+1} = 9+2 = 11 \quad \checkmark$
Induction hypothesis: $\quad 3^{3n+2}+2^{4n+1} = 11k$
$\begin{align} 3^{3(n+1)+2}+2^{4(n+1)+1} &= 27\cdot3^{3n+2}+16\cdot 2^{4n+1} \\
&= 22\cdot3^{3n+2}+5\cdot3^{3n+2}+11\cdot 2^{4n+1}+5\cdot 2^{4n+1}\\
&= 22\cdot3^{3n+2}+11\cdot 2^{4n+1}+5(3^{3n+2}+ 2^{4n+1})\\
&= 11(2\cdot3^{3n+2}+ 2^{4n+1})+5(11k)\\
&= 11(2\cdot3^{3n+2}+ 2^{4n+1}+5k)\quad \text{as required}\\
\end{align}$  

(without induction):
$3^3 \equiv 27 \equiv 5 \bmod 11$ and $2^4 \equiv 16 \equiv 5\bmod 11$ 
So $3^{3n+2}+2^{4n+1} \equiv 9\cdot 5^n+2\cdot 5^n \equiv 11\cdot 5^n \equiv 0 \bmod 11$
A: Note that any numbers of the form $C_n=Aa^n+Bb^n$ satisfy the recurrence $C_{n+2}=(a+b)C_{n+1}-abC_n$. From this it follows that any number which is a factor of $C_n$ and $C_{n+1}$ will divide all the $C_r$ for $r\ge n$. (one can reach conclusions about lower values of $r$ as well with a little care)
Here we have $C_n=9\cdot 27^n+2\cdot 16^n$ and $C_0=11, C_1=275$.
I mention it not because it is the easiest solution, but because it explains why this persistence of divisibility kind of problem is so prevalent, and makes it easy to construct a range of examples, which are normally practice for applying induction.
