Deductive proof in natural numbers - division Prove, using induction rule: 
$$\forall_{n\in N} \left (2^{2n+1} + 3n + 7 = 9c\right)$$ 
$$c\in N$$
1. I checked with 1 : works 
2. I assumed that it is true for some natural number k 
3. I plugged in $k+1$ and am now stuck, trying to get the original assumption.
 A: Hint:
$$
\left(2^{2n+3}+3(n+1)+7\right)-\left(2^{2n+1}+3n+7\right)=3\overbrace{(2\cdot4^n+1)}^{2\cdot1^n+1\pmod3}
$$
A: First, show that this is true for $n=1$:
$2^{2+1}+3+7=18$
Second, assume that this is true for $n$:
$2^{2n+1}+3n+7=9c$
Third, prove that this is true for $n+1$:
$2^{2(n+1)+1}+3(n+1)+7=$
$\color\red{2^{2n+1}+3n+7}+3(\color\green{2^{2n+1}+1})=$
$\color\red{9c}+3(\color\green{3k})=$
$9c+9k=$
$9(c+k)$
Please note that the assumption is used only in the part marked red.

Now let's prove by modular arithmetic that $2^{2n+1}+1=3k$:


*

*$n\equiv0\pmod3\implies2^{2n+1}+1\equiv2^{2\cdot0+1}+1\equiv 3\equiv0\pmod3$

*$n\equiv1\pmod3\implies2^{2n+1}+1\equiv2^{2\cdot1+1}+1\equiv 9\equiv0\pmod3$

*$n\equiv2\pmod3\implies2^{2n+1}+1\equiv2^{2\cdot2+1}+1\equiv33\equiv0\pmod3$

A: Now, since you have already known that $(2^{2k + 1} + 3k + 7) \vdots 9$, we'll now show that it'll still hold for $n = k + 1$, i.e, we need to show that:
$$(2^{2k + 3} + 3k + 10) \vdots 9$$
So, we'll have:
$$\begin{align}2^{2k + 3} + 3k + 10 &= 4\times 2^{2k + 1} + 3k + 10 \\
&=4\times (2^{2k + 1} \color{red}{+ 3k + 7}) \color{blue}{-12k - 28} + 3k + 10 \text{ (add, then subtract)} \\
&= \underbrace{\underbrace{4\times \underbrace{(2^{2k + 1} + 3k + 7)}_{\vdots 9}}_{\vdots 9} -\underbrace{9k}_{\vdots 9} - \underbrace{18}_{\vdots 9}}_{\vdots 9} \end{align}$$
A: Many inductive proofs of this and similar divisibilities boil down to computing the first two terms of the Binomial Theorem $\,\color{#0a0}{\rm BT}.\,$ However, this innate structure is often (greatly) obfuscated by details of the special case. Let's bring this structure to the fore and exploit it to the hilt. Doing so we will see how it greatly simplifies the inductive proof - so much so that the proof becomes obvious, and the arithmetic becomes so easy that it can all be done mentally.
Note $\  2^{\large 1+2n}\! = 2(2^{\large 2})^{\large n} = 2(1\!+\!3)^{\large n}\ $ and
$ {\rm mod}\,\ \color{#c00}{3^2}\!:\,\ 2(1\!+\!3)^{\large n}\,\overset{\color{#0a0}{\rm BT}}\equiv\, 2(1\!+\!3n)\equiv 2\!+\!6n\equiv -(7\!+\!3n),\ $ as sought
The inductive step of $\,\color{#0a0}{\rm BT}\,$ is much clearer without obfuscation by special-case cruft, viz.
$\!\begin{align}{\rm mod}\,\ \color{#c00}{a^2}\!:\,\  (1+ a)^n\, \ \  \equiv&\,\ \ 1 + na\qquad\qquad\ \ \ {\rm i.e.}\ \ P(n)\\[1pt]
\Rightarrow\ (1+a)^{\color{}{n+1}}\! \equiv &\  (1+na)(1 + a)\\[2pt] 
\equiv &\,\ \ 1+ na+a+n\color{#c00}{a^2}\\ 
 \equiv &\,\ \ 1\!+\! (n\!+\!1)a\qquad\quad {\rm i.e.}\ \ P(\color{}{n\!+\!1})\\  
  \end{align}$
