Prove by mathematical induction that

Question

Prove by mathematical induction that $$P(n)=3^{2n+1} + 2^{n-1}$$ is a multiple of 7.

My Attempt: Here, $P(n)= 3^{2n+1}+2^{n-1}$ For $n=1$, $$P(1)=3^3+2^0$$ $$=28$$ So, $P(1)$ is true. Suppose, $P(m)$ is true for all $m\in N$ Now, we have to show that $P(m+1)$ is true, $$P(m+1)=3^{2(m+1)+1}+2^{(m+1)-1}$$ $$=3^{2m+3}+2^m$$

Answer 1

Now, $$3^{2m+3}+2^m=9\cdot3^{2m+1}+2^m=9\left(3^{2m+1}+2^{m-1}-2^{m-1}\right)+2\cdot2^{m-1}=$$ $$=9\left(3^{2m+1}+2^{m-1}\right)-9\cdot2^{m-1}+2\cdot2^{m-1}=9\left(3^{2m+1}+2^{m-1}\right)-7\cdot2^{m-1}.$$ Can you end it now?

Answer 2

it is $$P(n+1)=3^{2n+3}+2^n$$ and we get $$P(n+1)-P(n)=3^{2n+1}\cdot 7+3^{2n+1}+2^{n-1}$$ therefore $$7|P(n+1)$$

Answer 3

Now, we have to show that $P(m+1)$ is true, $$P(m+1)=3^{2(m+1)+1}+2^{(m+1)-1}$$ $$=3^{2m+3}+2^m$$

You'll want to use the hypothesis of the inductive step ("$P(m)$ is true"); so rewrite: $$\begin{align} 3^{2m+3}+2^m & =3^2 \cdot 3^{2m+1}\color{red}{+2}\cdot 2^{m-1} \\[5pt] & =9 \cdot 3^{2m+1}\color{red}{+9}\cdot 2^{m-1}\color{red}{-7}\cdot 2^{m-1} \\[5pt] & = 9 \left(\color{blue}{3^{2m+1}+2^{m-1}} \right) - 7\cdot 2^{m-1} \end{align}$$ Now the first term is divisible by $7$ because (...) and the second term is (...).

Answer 4

Inductive Step $$ \begin{align} P(m+1) &=3^{2m+3}+2^m\\ &=9\cdot3^{2m+1}+2\cdot2^{m-1}\\ &=7\cdot3^{2m+1}+2\left(3^{2m+1}+2^{m-1}\right)\\ &=7\cdot3^{2m+1}+2P(m) \end{align} $$

---

Direct Proof

Note that since $2\cdot4\equiv1\pmod7$, we get $$ \begin{align} 3^{2k+1}+2^{k-1} &=3\cdot9^k+2^{-1}\cdot2^k\\ &\equiv3\cdot2^k+4\cdot2^k&\pmod7\\ &=7\cdot2^k\\ &\equiv0&\pmod7 \end{align} $$

Answer 5

There are several standard ways to cope with the problem. First, state $P(n)$ properly:

$P(n)$: for every $n\ge1$, there exists $k$ such that $3^{2n+1}+2^{n-1}=7k$

(variables are assumed to vary in the natural numbers).

$P(1)$: $3^{2+1}+2^{1-1}=3^3+1=28=7\cdot 4$

Therefore $P(1)$ is true.

Assume $P(n)$, that is, $3^{2n+1}=7k-2^{n-1}$ for some $k$. Then $$ 3^{2(n+1)+1}+2^{(n+1)-1}= 3^2\cdot 3^{2n+1}+2^n= 9\cdot 7k-9\cdot2^{n-1}+2\cdot2^{n-1}=7(9k-2^{n-1}) $$ Therefore we have proved that, for every $n\ge1$, $P(n)\implies P(n+1)$.