Deductive proof in natural numbers - division

Question

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.

Answer 1

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} $$

Answer 2

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$

Answer 3

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}$$