Induction Question: $7^n-6n-1=36m$

Question

---

In the end I get the following: $$(7^n-6k-1)+6(7^k-1)$$ I tell myself that $(7^n-6k-1)$ is clearly divisible by $36$ by the initial proposition, and that $6(7^k-1)$ is divisible by $36$ because $7^k-1$ is divisible by $6$ by the initial proposition. I'm just simply wondering if I've made an error in $\color{green}{\text{my reasoning}}$, that's all.

---

$$\color{green}{WORK}$$

Allow me to put forth the proposition that $7^n-6n-1=36m$ for all $n\in\mathbb{N}$ and for some $m\in\mathbb{N}$. Clearly this holds for $n=1$ as $36$ divides $0$. Now, let's say $n=k$ for some $k\in\mathbb{N}$ with $k>1$, and let's just say it holds, namely

$$7^k=6k-1=36p$$

holds. We need to show that this proposition holds for $k+1$ though. Let's do that now. Immediately we notice that

$$7^{k+1}-6(k+1)-1$$

reduces in the following manner:

$$7\cdot 7^k-6k-6-1$$

$$\downarrow$$

$$(6+1)7^k-6k-6-1$$

$$\downarrow$$

$$6\cdot 7^k+7^k-6k-6-1$$

$$\downarrow$$

$$\underset{\color{fuchsia}{\diamond}}{(7^k-6k-1)}+\underset{\color{blue}{\diamond}}{6(7^k-1)}$$

Now, notice that $\color{fuchsia}{\diamond}$ is clearly divisible by $36$ by the initial proposition, and so is $\color{blue}{\diamond}$ since $7^k-1$ is divisible by $6$ through the same proposition. Thus, by the principle of figuring-things-out-on-your-own-and-not-consulting-yahoo-answers-or-by-copying-your-friend's-answer, namely the Principle of Mathematical Induction, we have that

$$7^n-6n-1=36m$$

for all $n\in\mathbb{N}$ for some $m\in\mathbb{N}$. $\square$

---

Answer 1

We prove by induction that $36$ divides $7^n-6n-1$ for every positive integer $n$.

The result holds at $n=1$, since $7^1-(6)(1)-1=0$, and $36$ divides $0$.

Suppose that the result holds when $n$ is the particular integer $k$. We will show that the result holds when $n=k+1$. So we need to show that $36$ divides $7^{k+1}-6(k+1)-1$. We note, as you did, that $7^{k+1}=7\cdot 7^k=7^k+6\cdot 7^k$. Thus $$7^{k+1}-6(k+1)-1=7^k-6k-1+6(7^k-1).\tag{1}$$ By the induction assumption, $36$ divides $7^k-6k-1$. Also, by the induction assumption, $6$ divides $7^k-6k-1$, and therefore $6$ divides $7^k-1$. Thus $36$ divides $6(7^k-1)$. It follows that $36$ divides the right-hand side of (1), and therefore $36$ divides the right-hand side. That is what we needed to show.

Remark: Please note that the idea of the proof is the same as yours. However, we argued from the induction assumption $7^k-6k-1$ is divisible by $36$ to the conclusion that $7^{k+1}-6(k+1)-1$ is divisible by $36$.