Question

6n + n^7 is divisible by 7 and prove it in mathematical induction​

Answer 1

Answer:

Apply induction on $n$ (for integers $n \ge 1$) after showing that $\genfrac{(}{)}{0}{}{7}{j} = (7!) / (j! \, (7 - j)!)$ is divisible by $7$ for $j \in \lbrace 1,\, \dots,\, 6 \rbrace$.

Step-by-step explanation:

Lemma: $\genfrac{(}{)}{0}{}{7}{j} = (7!) / (j! \, (7 - j)!)$ is divisible by $7$ for $j \in \lbrace 1,\, 2,\, \dots,\, 6\rbrace$.

Proof: assume that for some $j \in \lbrace 1,\, 2,\, \dots,\, 6\rbrace$, $\genfrac{(}{)}{0}{}{7}{j}$ is not divisible by $7$.

The combination $\genfrac{(}{)}{0}{}{7}{j} = (7!) / (j! \, (7 - j)!)$ is known to be an integer. Rewrite the factorial $7!$ to obtain:

$\displaystyle \begin{pmatrix}7 \\ j\end{pmatrix} = \frac{7!}{j! \, (7 - j)!} = \frac{7 \times 6!}{j!\, (7 - j)!}$.

Note that $7$ (a prime number) is in the numerator of this expression for $\genfrac{(}{)}{0}{}{7}{j}\!$. Since all terms in this fraction are integers, the only way for $\genfrac{(}{)}{0}{}{7}{j}$ to be non-divisible by $7\!$ is for the denominator $j! \, (7 - j)!$ of this expression to be an integer multiple of $7\!\!$.

However, since $1 \le j \le 6$, the prime number $\!7$ would not a factor of $j!$. Similarly, since $1 \le 7 - j \le 6$, the prime number $7\!$ would not be a factor of $(7 - j)!$, either. Thus, $j! \, (7 - j)!$ would not be an integer multiple of the prime number $7$. Contradiction.

Proof of the original statement:

Base case: $n = 1$. Indeed $6 \times 1 + 1^{7} = 7$ is divisible by $7$.

Induction step: assume that for some integer $n \ge 1$, $(6\, n + n^{7})$ is divisible by $7$. Need to show that $(6\, (n + 1) + (n + 1)^{7})$ is also divisible by $7\!$.

Fact (derived from the binomial theorem $(\ast)$):

$\begin{aligned} & (n + 1)^{7} \\ &= \sum\limits_{j = 0}^{7} \left[\genfrac{(}{)}{0}{}{7}{j}\, n^{j}\right] && (\ast)\\ &= \genfrac{(}{)}{0}{}{7}{0} \, n^{0} + \genfrac{(}{)}{0}{}{7}{7} \, n^{7} + \sum\limits_{j = 1}^{6} \left[\genfrac{(}{)}{0}{}{7}{j}\, n^{j}\right] \\ &= 1 + n^{7} + \sum\limits_{j = 1}^{6} \left[\genfrac{(}{)}{0}{}{7}{j}\, n^{j}\right]\end{aligned}$.

Rewrite $(6\, (n + 1) + (n + 1)^{7})$ using this fact:

$\begin{aligned} & 6\, (n + 1) + (n + 1)^{7} \\ =\; & 6\, (n + 1) + \left(1 + n^{7} + \sum\limits_{j = 1}^{6} \left[\genfrac{(}{)}{0}{}{7}{j}\, n^{j}\right]\right) \\ =\; & 6\, n + n^{7} + 7 + \sum\limits_{j = 1}^{6} \left[\genfrac{(}{)}{0}{}{7}{j}\, n^{j}\right]\right) \end{aligned}$.

For this particular $n$, $(6\, n + n^{7})$ is divisible by $7$ by the induction hypothesis.

$\sum\limits_{j = 1}^{6} \left[\genfrac{(}{)}{0}{}{7}{j}\, n^{j}\right]$ is also divisible by $7$ since $n$ is an integer and (by lemma) each of the coefficients $\genfrac{(}{)}{0}{}{7}{j} = (7!) / (j! \, (7 - j)!)$ is divisible by $7\!$.

Therefore, $6\, (n + 1) + (n + 1)^{7}$, which is equal to $6\, n + n^{7} + 7 + \sum\limits_{j = 1}^{6} \left[\genfrac{(}{)}{0}{}{7}{j}\, n^{j}\right]\right)$, is divisible by $7$.

In other words, for any integer $n \ge 1$, if $(6\, n + n^{7})$ is divisible by $7$, then $6\, (n + 1) + (n + 1)^{7}$ would also be divisible by $7\!$.

Therefore, $(6\, n + n^{7})$ is divisible by $7$ for all integers $n \ge 1$.