Prove that $5^n + 6^n -1$ is divisble by 10 for all positive integers n. I know the base case is:
$$ n=1,
5^1+6^1-1=10,10|10
$$
But I am struggling about how to go about the inductive step.
 A: Let $x_n = 5^n + 6^n -1$. Then
$
y_n= x_{n+1}-x_n = 4 \cdot 5^n + 5 \cdot 6^n
$
is clearly a multiple of both $2$ and $5$, hence of $10$.
Thus, $x_{n+1}=x_n+y_n$ is a multiple of $10$, since by induction $x_n$ is a multiple of $10$.
A: Without induction you can prove a stronger result.
Note that $5^n$ always ends up with a $5$
Also $6^m$ always ends up with a $6$ so  $6^m-1$ ends up with a $5$
Thus $5^n + 6^m-1$ always ends up with a $0$ and it is a multiple of $10$.
If you insist on induction then the induction step follows $$5^{n+1}+6^{n+1}-1 = 5(5^n+6^n-1)+(6^n+4)$$ which is a multiple of $10$
A: Assume the hypothesis $5^i+6^i\equiv 1\bmod 10$ true for $i=1,\dots,n$.
We have 
\begin{align}5^{n+1}+6^{n+1}&=11(5^{n}+6^n)-30(5^{n-1}+6^{n-1})\\
&\equiv 11(1)-30(1)\bmod 10\\
&\equiv 1\bmod 10.
\end{align}
So, the hypothesis is also true for $n+1$.
Although, I prefer the proof that is not by induction by just noting that $5^n$ always ends in $5$ and $6^n$ always ends in $6$. So, $5^n+6^n-1\equiv 5+6-1\equiv 0\bmod 10$.
A: $5^n-1$ is even implies that $5^n+6^n-1$ is divisible by $2$,
$6^n-1=(6-1)(6^{n-1}-1+..)$ ($6=1$ mod $5$ implies that $6^n=1$ mod $5$ and $6^n-1=0$ mod $5$) implies that $5^n+6^n-1$ is divisible by $5$.
Recursive proof
$5^{n+1}+6^{n+1}-1=5.5^n+(5+1)6^n-1=5(5^n+6^n-1)+6^n+4$
Suppose that $6^n=6$ mod $10$, $6^{n+1}=36=6 $ mod $10$   implies that $6^n+4=0$ mod $10$.
A: Exploiting innate $\rm\color{#c00}{symmetry}$ yields a much more general result. Notice
$\qquad\phantom{\Rightarrow}\ \  \{ 5,\ \ \ \ 6\}\ \  \equiv\, \{0,\ \ \ 1\}\ \ \ \ {\rm mod}\,\ 5\ \&\ 2,\ $ since $\ \ \begin{align}&5,\,6\,\equiv\, 0,\, 1\,\bmod{5}\\ &5,\,6\,\equiv\, 1,\, 0\,\bmod{2}\end{align}$
$\qquad\Rightarrow\ \{5^n,\ \ 6^n\} \equiv \{0^n,\ \,1^n\}\,\ {\rm mod}\,\ 5\ \&\ 2,\ \ $ by the Congruence Power Rule 
$\qquad\Rightarrow\ \ \, 5^n\!+ 6^n\ \ \equiv \ \ 0^n\!+1^n\ \ \,{\rm mod}\,\ 5\ \&\ 2,\ \ $ so also $\,{\rm mod}\ 10 = {\rm lcm}(5,2)$ 
since addition $\,f(x,y)\, =\, x + y\ $ is $\rm\color{#c00}{symmetric}$ $\,f(x,y)= f(y,x),\ $  therefore its value depends only upon the (multi-)set $\,\{x,\,y\}.\ $  Below is a less trivial example.
$\qquad\phantom{\Rightarrow}\ \  \{ 52,\ \ \ \ 23\}\ \  \equiv\, \{2,\ \ \ 3\}\ \ \ \ {\rm mod}\,\ 7\ \&\ 10,\ $ since $\ \ \begin{align}&52,\,23\,\equiv\, 3,\, 2\,\bmod{7}\\ &52,\,23\,\equiv\, 2,\, 3\,\bmod{10}\end{align}$
$\qquad\Rightarrow\ \{52^n,\ \ 23^n\} \equiv \{2^n,\ \,3^n\}\,\ {\rm mod}\,\ 7 \ \&\ 10,\ $ by the Congruence Power Rule 
$\qquad\Rightarrow\ \ \ 52^n\!+\! 23^n\ \ \equiv \ \ 2^n\!+3^n\ \ \,{\rm mod}\,\ 7\ \&\ 10,\  $ so also $\,{\rm mod}\ 70 = {\rm lcm}(7,10)$
Generally $ $ if a polynomial $\,f\in\Bbb Z[x,y]\,$ is $\rm\color{#c00}{symmetric}$ then
$\qquad\qquad\quad \{A, B\}\, \equiv\, \{a,b\}\,\ {\rm mod}\,\ m\ \&\ n\ \Rightarrow\  f(A,B)\equiv f(a,b)\, \pmod{\!{\rm lcm}(m,n)}\qquad\quad$
a generalization of the constant-case optimization  of CRT = Chinese Remainder Theorem,  combined with a generalization of the Polynomial Congruence Rule to (symmetric) bivariate polynomials.
Remark $ $ This proof does (implicitly) use induction when we raise the congruences to power $\,n\,$ using the Congruence Power Rule (whose linked proof is indeed by induction on $\,n,\,$ using the Congruence Product Rule in the inductive step).
