Proving $7|13\cdot 6^{n}+8\cdot 13^{n}$ for all natural numbers.

Question

I would like to verify whether my proof is correct. The answer sheet used a much more intuitive and logical approach but I think mine is correct also.

---

To prove: $7|13\cdot 6^{n}+8\cdot 13^{n}$ for all natural numbers

Proof: We proceed by induction and show the base case holds. $13+8=21 $. Since 7 divides 21 the base case holds.

We assume $7|13\cdot 6^{m}+8\cdot 13^{m}$ and we need to show $7|13\cdot6^{m+1}+8\cdot 13^{m+1}$.

Since, $7|13\cdot 6^{m}+8\cdot 13^{m}$, we have, $13\cdot 6^{m}+8\cdot 13^{m} =7x, \space x \in \mathbb{N}$.

We rewrite $13\cdot 6^{m+1}+8\cdot 13^{m+1}$ as $6(13\cdot 6^m)+13(8\cdot 13^m)$ and notice, $13\cdot 6^m=7x-8\cdot13^m$.

We substitute and find,

$6(7x-8\cdot13^m)+13(8\cdot13^m)=42x-48\cdot13^m+104\cdot13^m = 42x+56\cdot13^m=7(6x+8\cdot13^m)$

Since $6x+8\cdot13^m \space \in \mathbb{N}$

$\\ \therefore $ By the principle of mathematical induction, $7|13\cdot 6^{n}+8\cdot 13^{n}$ for all natural numbers $n \space \blacksquare$.

Answer 1

Per your comment, we simplify your inductive proof to highlight the relationship with congruence-based proofs. Your proof can be viewed as scaling by $\color{#c00}{13 = 6+7}\,$ the hypothesized equation $\,P(n)$

$$\begin{align} (\color{#c00}{13=6+7})\,\ {\rm times}\,\ (\overbrace{a\,13^{\large n}\ +\ \ b\,6^{\large n}\ \!=\ 7k}^{\Large P(n)})\qquad\quad&\\[.3em] \Longrightarrow\ \ \ \underbrace{a\,13^{\large n+1} + b\,6^{\large n+1}\ =\,\ 7(13k-b\,6^n)}_{\Large P(n+1)} \end{align}\qquad\qquad$$

Its arithmetical essence is clearer $\bmod 7\,$ using congruences and the Congruence Product Rule

$$\begin{align} \color{#c00}{13}\,&\equiv\, \color{#c00}6\\[.3em] \times\ \ \quad a\,13^{\large n}&\equiv -b\,6^{\large n}\quad \qquad P(n)\\[1em] \hline \Rightarrow\ a\,13^{\large n+1}&\equiv -b\,6^{\large n+1}\qquad P(n+1) \end{align}\quad \qquad$$

where $\,a,b = 8,13$ in your case. In this answer I explain at length how the inductive proofs are nothing but special cases of the proofs of the Congruence Product Rule. As above, it is much clearer to use the rule as a lemma (call by name) rather the repeat its proof inline (call by value) in the special case at hand.

Answer 2

It is correct, but:

• When you wrote that “We rewrite $13\cdot 6^{m}+8\cdot 13^{m}$ as $6(13\cdot 6^m)+13(8\cdot 13^m)$”, what you meant was “We rewrite $13\cdot 6^{m+1}+8\cdot 13^{m+1}$ as $6(13\cdot 6^m)+13(8\cdot 13^m)$”.
• You don't need to compute $6\times8$ and $13\times8$. Note that\begin{align}6(7x-8\times13^m)+13(8\times13^m)&=7\times(6x)+(-6+13)\times(8\times13^m)\\&=7\times(6x+8\times13^m).\end{align}

Answer 3

$$13\cdot 6^{n}+8\cdot 13^{n}\equiv (-1)(-1)^n+(1)(-1)^n =0 \text { mod (7) }$$

Answer 4

Rewrite $13\cdot 6^n+8\cdot 13^n$ in base $7$: $$16\cdot 6^n+11\cdot 16^n$$

Note that $6\cdot 6=51$ in base $7$.

The first term ends with $1$ if $n$ is even and ends with $6$ if $n$ is odd. Conversely, the second term ends with $1$ if $n$ is even and ends with $6$ if $n$ is odd. Therefore, the sum ends with $0$.