Question

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

Answer 1

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`.

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} = (7!)/(j! \, (7 - j)!) = (7 * 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 * 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`.