Prove $9 \mathrel| (4^n+6n-1)$ by induction

Question

I know that this question was already answered, but I would like to know if the second step of induction its okay the way I did it.

This question is different from Induction proof for $n\in\mathbb N$, $9 \mathrel| (4^n+6n-1)$ and Let $n ∈ N, n ≥ 1$. Prove that $4^n + 6n - 1$ is divisible by $9$. since it is just about to check a part from a proof that I did (if the way I thought is correct or not).

Suppose that $9 \mathrel| (4^k+6k-1)$ is true for $k\in \mathbb{N}, k\geq1$. I want to prove $P(k+1)$: $ 9 \mathrel| 4^{(k+1)} +6(k+1) - 1$

Since $9 \mathrel| (4^k+6k-1)$, I can rewrite as:

$4^k+6k-1 = 9q$, where $q \in \mathbb{Z} $. By the definion of Divisibility.

• Multiplying the equation on both sides by 4, I'll get:

$4^{(k+1)} +24k-4 = 36q$

• Adding 3 on both sides

$4^{(k+1)} +24k - 1 = 36q + 3$

• Subtracting $18k$ on both sides

$4^{(k+1)} +6k - 1 = 36q + 3 -18k$

• Adding 6 in order to have $6(k+1)$ as a factor

$4^{(k+1)} +6k + 6 - 1 = 36q + 3 -18k + 6$

$4^{(k+1)} +6(k+1) - 1 = 36q + 9 -18k $

Note that $36q + 9 -18k$ can be written like this: $9(4q + 1 - 2k)$. Thus $9Q$, $Q=(4q + 1 - 2k), Q \in \mathbb{Z}$.

Therefore:

• $4^{(k+1)} +6(k+1) - 1 = 9Q$. Which means that $4^{(k+1)} +6(k+1) - 1$ is also divided by 9.

Does my proof look fine? If there is a problem, please tell me. All help is appreciated.

Answer 1

It's good. I like it a lot.

But in induction proofs it's often easier to start at the destination and drive backwards through one way streets to the start, rather than starting from the start and driving through a bunch of intersections without a map in order to reach your destination.

$4^{k+1} + 6(k+1) - 1=$

$4*4^{k} + 6k + 5 = $

$4(4^k + 6k -1) - 24k +4 +6k + 5=$

$4(4^k + 6k -1) - 18k +9 = 4(4^k+6k-1) -9(2k-1)$.

And $9|4^k + 6k -1\implies 9|4(4^k+ 6-1) - 9(2k-1)$$

Answer 2

It's fine. Cut to the essentials: just say if $P(k)=9q$ for some $q$ then $P(k+1)=9(4q-2k+1)$, with some minimal computations to justify it:

$$P(k+1)=4^{k+1} + 6(k+1)-1 = 4(4^k) + 6k +5 =\\ 4(9q-6k+1)+ 6k+5 = 36q - 18k + 9 = 9(4q-2k+1)$$

No "cleverness" needed, it just falls out automatically.

Answer 3

If $n \equiv 0 \pmod 3$, then for an integer $k$:

$$4^n + 6n-1 \equiv 4^{3k} + 18k - 1 \equiv 1^k + 0 - 1 \equiv 0 \pmod 9.$$

If $n \equiv 1 \pmod 3$, then:

$$4^n + 6n-1 \equiv 4 \cdot4^{3k} + 18k + 6- 1 \equiv 4+0+6-1 \equiv 0 \pmod 9.$$

Finally, if $n \equiv 2 \pmod 3$, we have:

$$4^n + 6n-1 \equiv 16 \cdot4^{3k} + 18k + 12- 1 \equiv 16+0+12-1 \equiv 0 \pmod 9.$$

Since an integer can only congruent to either $0 \pmod 3, 1 \pmod 3$ or $2 \pmod 3$, this completes the proof for all integer $n$.

Answer 4

It is fine. The same work with congruence: $$4^k+6k-1\equiv 0 \pmod{9}$$ Since $gcd(4,9)=1$, multiply it by $4$: $$4^{k+1}+24k-4\equiv 4^{k+1}+\require{cancel}\cancel{18k}+6k-4+\color{red}9\equiv 4^{k+1}+6(k+1)-1\equiv 0\pmod{9}.$$

Answer 5

There is an easier way: $4^n+6n-1\iff (3+1)^n+6n-1=(9M+3n+1)+6n-1=9(M+n)$