$13\mid(3^{n+2}+4^{2\cdot n+1})$. Is my arithmetical proof using induction correct?

Question

The exercise 2.b of my textbook ask me to prove that: $$\text{(P): }\;\forall n\in \mathbb{N}, 13\;|\;(3^{n+2}+4^{2\cdot n+1})$$

I would like to know if my proof is correct and if not what I need to make it correct:

$$P\iff \forall n\in \mathbb{N}\;\exists \;q\in\mathbb{N}\;\text{such that }13 \cdot q = \;(3^{n+2}+4^{2\cdot n+1})$$

$$\text{P(1):} \; 3^3+4^3=91\;\text{which is equal to }13\cdot 7\\ \text{Let assume that P(k) is true for some k }\in \mathbb{N},\\13 \cdot q = \;(3^{n+2}+4^{2\cdot n+1})\\3\cdot 4\cdot(13 \cdot q )= \;(3^{n+2}+4^{2\cdot n+1})\cdot 3\cdot4\\ 13 \cdot (12\cdot q) = \;(4\cdot3^{n+3}+3\cdot4^{2\cdot n+2})\\\text{P(n) imply P(n+1) thus P(n) is true for all natural numbers n}$$

Answer 1

Basically you did it all right but you missed the last step.Namely you have the first step of induction P(1) done(usually called the base case).Now you have the hypothesis that P(k) is true which implies that $13| 3^{k+2} + 4^{2k +1}$ from which we can conclude follwing for some natural number $q$:

$$13q = 3^{k+2} +4^{2k+1} \implies 13q-4^{2k+1}=3^{k+2}$$

Now to conclude your proof and make it right we need to prove the P(k+1) which comes to :

$$3^{(k+1)+2} + 4^{2(k+1)+1} = 3^{k+2}3^1 + 4^{2k+1}4^2$$ $$=(13q-4^{2k+1})3 + 16\cdot4^{2k+1}$$ $$= 39q -3\cdot 4^{2k+1} + 16\cdot 4^{2k+1}$$ $$= 39q+13\cdot4^{2k+1}=13(13q + 4^{2k+1})$$

And thus from the last form we can see that it is obviously divisible by 13.And that would be correct proof

Answer 2

Your proof is not correct. You have proven that $P(n)$ implies $$13 | (4\cdot 3^{n+1} + 3\cdot 4^{2n + 2})$$ which is not the same as $P(n+1)$. You need to prove $P(n+1)$, which is equal to $$13| (3^{(n+1)+2} + 4^{2(n+1) + 1})$$

Answer 3

If $P(n):13|(3^{n+2}+4^{2n+1})$ holds true for $n=m$

$13|(3^{m+2}+4^{2m+1})$

Now,$3^{(m+1)+2}+4^{2(m+1)+1}-3(3^{m+2}+4^{2m+1})=4^{2m+1}(4^2-3)$ which is divisible by $13$

So, $P(n)$ will hold true for $n=m+1$ iff $P(n)$ will hold true for $n=m$

Now you have already established the base case.

---

If induction is not mandatory,

$3^{n+2}+4^{2n+1}=9\cdot3^n+4\cdot16^n\equiv9\cdot3^n+4\cdot3^n\pmod{13}$ as $16\equiv3\pmod{13}$

$\implies3^{n+2}+4^{2n+1}\equiv3^n(9+4)$