0

Prove by induction that $6^n + 4$ is divisible by $5$.

Using another method I found that the solution is $5\cdot6^k$ when i saw the solution using induction they made an assumption, where $6^k + 4 = 5m$, reaching, $6\cdot6^k + 4$. Their final answer was $5\cdot6^k$ as well . Now my question is did they replace $5m$ in the equation $6\cdot6^k + 4$, and why did they assume $m=1$?

Anton Vrdoljak
  • 2,717
Maxwell
  • 11
  • Do you the statement of the principle of mathematical induction? Please take a look here $:$ https://en.m.wikipedia.org/wiki/Mathematical_induction – math maniac. May 19 '20 at 06:23
  • To say that a number $6^n+4$ is divisible by $5$ means that it must be a multiple of $5$, i.e. that $6^n+4=5 \times m$ for some $m$. – Mauro ALLEGRANZA May 19 '20 at 06:27
  • First of all there is a base case. In this problem the base case is to show that the result holds for $n=1$ which is indeed true here. Then there is a inductive stage known as induction hypothesis where you assume the result to be true for $n=m,$ for some positive integer $m \geq 1.$ Now try to show that the result is true for $n = m+1$ assuming the induction hypothesis. If you can able to show that then The principle of mathematical induction guarantees that the result is true for all $n \geq 1.$ – math maniac. May 19 '20 at 06:28
  • can you clarify on the part of your question of what do you mean by they assume $m=1$? I think more context is needed to understand your question. – Siong Thye Goh May 19 '20 at 06:28
  • So, a proof by induction must start with the Base case: $n=1$ and amounts to show that $6^1+4=6+4=10=5 \times m$ for some $m$ (quite easy). – Mauro ALLEGRANZA May 19 '20 at 06:32
  • 1
    If you use $6^m\equiv 1\text{ mod} 5$ you find a very nice solution without induction, though – IMOPUTFIE May 19 '20 at 09:10

2 Answers2

1

Mathematical induction is a good way to prove that a statement is true for all $n\in\mathbb{N}$.

Base case: $n=0\Rightarrow 6^n+4=5$ is divisible by $5$.

Inductive hypothesis: $6^k+4$ is divisible by $5$ for all $k\le n$.

The idea is to try to prove from this, that $6^{k+1}+4$ is also divisible by $5$.

A convenient way is just to take the difference between the $k+1$ case and the $k$ case, and show that it is divisible by 5.

Calculation:

$6^{k+1}+4 - (6^{k}+4) = 6\times6^k - 6^k = 5\times 6^k$.

By the principle of mathematical induction we are done.$\blacksquare$

Benjamin Wang
  • 3,920
0

Let $S$ be the set of positive integers such that $6^n+4$ is divisible by $5$. Then

  • $1\in S$, because $10$ is divisible by $5$

Assume that $n$ is in $S$, for some positive integer $n$, that is assume you have proved that

  • $6^n+4=5m$, for some integer $m$.

Then

  • $n+1\in S$

because \begin{align*} 6^{n+1}+4&=6\cdot 6^n+4\nonumber\\ &=6\cdot 5m-20\nonumber\\ &=5(6m-4)\nonumber\\ &=5k\nonumber \end{align*} Hence by induction $S=\mathbb{N}$.

Maryam
  • 1,889