Prove by mathematical induction that $(7n + 1)6^n + (−1)^{n+1}$ is divisible by $49$ for all $n \in \mathbb{Z}^+$.

Question

Here is my solution so far: Inductive step: Assume $P(k)$ is true, i.e.

$(7k+1)6^k+(-1)^{k+1} = 49q $, $q$ belong to $z(IH)$

when $n = k + 1$:

$$P(k + 1) = 49 \mid (7(k+1)+1)6^{k+1}+(-1)^{k+1}$$ $$ = 49 \mid (7k+7+1)6^{k+1}+(-1)^{k+1}$$ $$ = 49 \mid 6(7k+1)6^k+7(6^{k+1})+(-1)^{k+1}$$ $$ = 49 \mid 6((7k+1)6^k+(-1)^{k+1})-6(-1)^{k+1}+7(6^{k+1})+(-1)^{k+1} $$ $$ = 49 \mid 6(49q)-6(-1)^{k+1}+7(6^{k+1})+(-1)^{k+1}$$ $$ = 49 \mid 6(49q)-7(-1)^{k+1}+42(6^k)$$ $$ = 49 \mid 6(49q)+7(-1)^k+42(6^k)$$

then idk how to solve it, am I doing something wrong?

Answer 1

I don't know whether you have done it, but when writing a proof by induction, it is important to show that the base case $P(1)$ holds.

Anyways, I believe that there is a simple error in your first step - when you consider $n=k+1$, we should have $(-1)^{n+1}=(-1)^{k+2}$, not $(-1)^{k+1}$ as per what you wrote.

Answer 2

Step 1:

$n=1$ then $7\times 6 +(-1)^2=49$ is divisible by $49$

Step 2:

Assume that for $n=k$, $(7k+1)\times 6^k + (-1)^{k+1}$ divisible by $49$

then

$n=k+1$, $$(7k+8)\times 6^{k+1} + (-1)^{k+2}=(7k+1+7)\times 6^{k+1} + (-1)^{k+2}=$$ $$=6^{k+1}\times(7k+1)+7\times 6^{k+1} - (-1)^{k+1}=$$ $$=6\times [(7k+1)\times 6^k + (-1)^{k+1}] + 7\times 6^{k+1} - 7\times (-1)^{k+1}=$$ $$=6\times [(7k+1)\times 6^k + (-1)^{k+1}] + 7\times (6^{k+1} - (-1)^{k+1})=$$ $$=6\times [(7k+1)\times 6^k + (-1)^{k+1}] + 7\times [(6-(-1))\times((6^k + 6^{k-1}(-1) + 6^{k-2}(-1)^2 + ... + (-1)^k)]=$$ $$=6\times [(7k+1)\times 6^k + (-1)^{k+1}] + 49\times (6^k + 6^{k-1}(-1) + 6^{k-2}(-1)^2 + ... + (-1)^k)=$$ is divisible by $49$

then

$(7n + 1)6^n + (−1)^{n+1}$ is divisible by $49$ for all $n \in \mathbb{Z}^+$.

from your solution: $$6(49q)+7(-1)^k+42(6^k)=6(49q)+7[6^{k+1} -(-1)^{k+1}]$$

Answer 3

There are three formal issues.

1. It is not clear what you mean by $P(k)$. When you write "Assume $P(k)$ is true", it seems to be a logical proposition. But then you write $P(k) = \ldots$ which indicates that it abbreviates the expression $(7k+1)6^k+(-1)^{k+1}$.
   The proper interpretation of $P(k)$ should be that $(7n + 1)6^n + (−1)^{n+1}$ is divisible by $49$.

2. You do not consider the base case. You can take $k=0$ which produces $1\cdot 6^0 + (-1)^1 = 0$ or $k = 1$ which produces $(7+1)\cdot6^1 +(-1)^2 = 49$. Both are divisible by $49$.

3. In the inductive step you should have considered $$(7(k+1)+1)6^{k+1}+(-1)^{k+2} .$$ Nevertheless it is true that you get $$6(49q)+7(-1)^k+42(6^k)$$ because your calculation $$6(49q)-6(-1)^{k+1}+7(6^{k+1})+(-1)^{k+1} =6(49q)-7(-1)^{k+1}+42(6^k)$$ is incorrect. Working with $(-1)^{k+2}$ on the LHS makes it correct.

Since $-7(-1)^{k+1}+42(6^k) = 7(-1)^k+42(6^k) = 7((-1)^k + 6^{k+1})$, it suffices to prove that $(-1)^k + 6^{k+1}$ is divisible by $7$ for all $k$.

Perhaps the simplest way to do it is to calculate$\mod 7$. Letting $[n]$ denote the residue class of $n \mod 7$, we get $$[(-1)^k + 6^{k+1}] = [-1]^k + [6]^{k+1} = [-1]^k + [-1]^{k+1} = [0].$$

Answer 4

We continue from where you left off. Given the predicate $P(k)$:

$$ P(k) = 49 \mid (7k + 1) 6^k + (-1)^{k + 1} $$

You deduced $P(k + 1)$ to be:

$$ P(k + 1) = 49 \mid 7(−1)^k + 42 \cdot 6^k \wedge P(k) $$

Now, since we assume $P(k)$ holds it remains to show that $49 \mid 7(−1)^k + 42 \cdot 6^k$. We do so inductively. First we divide by $7$, getting:

$$ Q(k) = 7 \mid (-1)^k + 6^{k + 1} $$

We now show $Q(k)$ holds for all naturals. We consider two cases, these being that $k$ is even or odd. If $k$ is even $Q(k)$ is:

$$ Q(k) = 7 \mid 1 + 6^{k + 1} = 7 \mid 1 + 6 \cdot 6^k $$

This means $Q(k + 2)$ is:

$$ Q(k + 2) = 7 \mid 1 + 36 \cdot 6 \cdot 6^k = 7 \mid 1 + 6 \cdot 6^k + 6 \cdot 35 \cdot 6^k = 7 \mid 6 \cdot 35 \cdot 6^k \wedge Q(k) $$

Now, the base case $Q(0)$ holds therefore $Q(k)$ holds for all even $k$. If $k$ is odd $Q(k)$ becomes:

$$ Q(k) = 7 \mid -1 + 6 \cdot 6^k $$

In this case $Q(k + 2)$ is:

$$ Q(k + 2) = 7 \mid -1 + 6 \cdot 36 \cdot 6^k = 7 \mid -1 + 6 \cdot 6^k + 6 \cdot 35 \cdot 6^k = 7 \mid 6 \cdot 35 \cdot 6^k \wedge Q(k) $$

The base case for odd $k$ $Q(1)$ holds and so $Q(k)$ holds for all odd $k$. This implies $P(k)$ holds for all naturals.