Welcome to our community

Be a part of something great, join today!

Induction for divisibility by 10

KOO

New member
Oct 19, 2013
19
Show that for every n∈N, 34n+2 +1 is divisible by 10

Prove by Induction.


Attempt)

Base Case: n = 1, 3(4(1)+2) + 1 = 730
So the base case holds true.

Assume that the inequality holds for n = k

34k+2 +1 is divisible by 10

Show true for n = k+1

34(k+1)+2 + 1
34k+4+2 + 1
34 * 34k+2 + 1
81 * 34k+2 + 1
(80+1) * 34k+2 + 1
80(34k+2) + 34k+2 + 1

80(34k+2) + 34k+2 + 1 is divisible by 10 according to our induction hypotheses.


What next?
 
Last edited:

Petrus

Well-known member
Feb 21, 2013
739
Show that for every n∈N, 34n+2 +1 is divisible by 10

Prove by Induction.


Attempt)

Base Case: n = 1, 3(4(1)+2) + 1 = 730
So the base case holds true.

Assume that the inequality holds for n = k

34k+2 +1 is divisible by 10

Show true for n = k+1

34(k+1)+2 + 1
34k+4+2 + 1
34 * 34k+2 + 1
81 * 34k+2 + 1
(80+1) * 34k+2 + 1
80(34k+2) + 34k+2 + 1

80(34k+2) + 34k+2 + 1 is divisible by 10 according to our induction hypotheses.


What next?
\(\displaystyle 3^{4k+2}=3^{2(2k+1)}=9^{2k+1}=(10-1)^{2k+1}\)
Regards,
\(\displaystyle |\pi\rangle\)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,779
Hi KOO! :)

Let me continue from one of your expressions:
\begin{aligned}
81 \cdot 3^{4k+2} +1
&= 81 \cdot \left(3^{4k+2} + 1\right) - 81 + 1 \\
&= 81 \cdot \left(3^{4k+2} + 1\right) - 80
\end{aligned}

Both $\left(3^{4k+2} + 1\right)$ and $80$ are divisible by $10$...
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
Re: Induction:

I would make my induction hypothesis $P_k$ be:

\(\displaystyle 3^{4k+2}+1=10m_k\) where \(\displaystyle m_k\in\mathbb{N}\)

Next, as my inductive step, I would look at:

\(\displaystyle \left(3^{4(k+1)+2}+1 \right)-\left(3^{4k+2}+1 \right)=3^{4k+2}\left(3^4-1 \right)=80\cdot3^{4k+2}\)

Adding this to $P_k$, we find:

\(\displaystyle 3^{4(k+1)+2}+1=10m_k+80\cdot3^{4k+2}=10\left(m_k+8\cdot3^{4k+2} \right)\)

If we use the recursive definition:

\(\displaystyle m_{k+1}=m_k+8\cdot3^{4k+2}\) where \(\displaystyle m_1=730\)

then we may write:

\(\displaystyle 3^{4(k+1)+2}+1=10m_{k+1}\)

Thus, we have derived $P_{k+1}$ from $P_k$ thereby completing the proof by induction.