Prove 7 divides $15^n+6$ with mathematical induction Prove that for all natural numbers statement n, statement is dividable by 7 
$$15^n+6$$
Base. We prove the statement for $n = 1$
15 + 6 = 21 it is true
Inductive step.
Induction Hypothesis. We assume the result holds for $k$. That is, we assume that
$15^k+6$
is divisible by 7
To prove: We need to show that the result holds for $k+1$, that is, that
$15^{k+1}+6=15^k\cdot 15+6$
and I don't know what to do 
 A: By induction hypothesis, you have $15^k=7t-6$.
A: Often textbook solutions to induction problems like this are magically "pulled out of a hat" - completely devoid of intuition. Below I explain the intuition behind the induction in this proof. Namely, I show that the proof easily reduces to the completely trivial induction that $\rm\ \color{#c00}{1^n \equiv 1}$.
Since $\rm\ 15^n + 6 = 15^n-1 + 7\:,\: $ it suffices to show that $\rm\ 7\ |\ 15^n - 1\:.\: $ The base case $\rm\ n=1\ $ is clear. The inductive step, slightly abstracted, is simply the following
$\ \ \ \ \ \ \ \begin{align} &7\ |\ \ \color{#0a0}{c\ -1},\ \ \ \color{#90f}{d\ -\ 1}\ \ \Rightarrow\ \ 7\ |\ cd\,-\,1 = (\color{#0a0}{c-1})\ d + \color{#90f}{d-1}\\[.2em]
{\rm thus} \ \ \ \ &7\ |\ 15-1,\ 15^n-1\ \ \Rightarrow\ \ 7\ |\ 15^{n+1}-1\end{align}$
$\rm Said\ \ mod\ 7,\ \ 15\equiv 1\ \Rightarrow\ 15^n\equiv \color{#c00}{1^n\equiv 1}\ $ by inductively multiplying ("powering") using this:
Lemma $\rm\ \ \ \ \ A\equiv a,\ \ B\equiv b\ \Rightarrow\ AB\equiv ab\ \ (mod\ m)\quad\ $ [Congruence Product Rule)
Proof $\rm\ \ m\: |\: A-a,\:\:\ B-b\ \Rightarrow\ m\ |\ (A-a)\ B + a\ (B-b)\ =\ AB - ab $
Notice how this transformation from divisibility form to congruence arithmetic form has served to reduce the induction to the triviality $\rm\, \color{#c00}{1^n \equiv 1}$. Many induction problems can similarly be reduced to trivial inductions by appropriate conceptual preprocessing. Always think before calculating!
See here and here for much further discussion on this topic.
A: Observe that $14$ is divisible by 7. Then let $15^k\cdot 15+6=15^k\cdot 14+ 15^k+6$. 
