Welcome to our community

Be a part of something great, join today!

[ASK] Mathematical Induction: Prove 7^n-2^n is divisible by 5.

Monoxdifly

Well-known member
Aug 6, 2015
269
Prove by mathematical induction that \(\displaystyle 7^n-2^n\) is divisible by 5.


What I've done so far:


For n = 1

\(\displaystyle 7^1-2^1=7-2=5\) (true that it is divisible by 5)

For n = k

\(\displaystyle 7^k-2^k=5a\) (assumed to be true that it is divisible by 5)

For n = k + 1

\(\displaystyle 7^{k+1}-2^{k+1}=7^k\cdot7-2^k\cdot2=7(7^k-2^k)+12\cdot2^k=7(5a)+12\cdot2^k\)

This is where the problem lies. How can I show that \(\displaystyle 12\cdot2^k\) is divisible by 5?
 

castor28

Well-known member
MHB Math Scholar
Oct 18, 2017
242
Prove by mathematical induction that \(\displaystyle 7^n-2^n\) is divisible by 5.


What I've done so far:


For n = 1

\(\displaystyle 7^1-2^1=7-2=5\) (true that it is divisible by 5)

For n = k

\(\displaystyle 7^k-2^k=5a\) (assumed to be true that it is divisible by 5)

For n = k + 1

\(\displaystyle 7^{k+1}-2^{k+1}=7^k\cdot7-2^k\cdot2=7(7^k-2^k)+12\cdot2^k=7(5a)+12\cdot2^k\)

This is where the problem lies. How can I show that \(\displaystyle 12\cdot2^k\) is divisible by 5?
Hi Monoxdifly ,

$12\cdot2^k$ is certainly not divisible by $5$ (look at the prime factors).

You made a mistake in your calculation: I get:
$$
7^k\cdot7 - 2^k\cdot2 = 7(7^k-2^k) + 5\cdot2^k
$$
and this should clear things up.
 

Monoxdifly

Well-known member
Aug 6, 2015
269
Ah, I see. Thank you very much!
 

Prove It

Well-known member
MHB Math Helper
Jan 26, 2012
1,403
It seems a bit overkill to use Induction, when there's a simple rule for the Difference of Two Terms With the Same Power...

$\displaystyle \begin{align*} a^n - b^n \equiv \left( a - b \right) \sum_{r = 0}^{n - 1}{ a^{n - 1 - r}\,b^r } \end{align*}$

so in your case the factor would be (7 - 2) which equals 5.
 

Monoxdifly

Well-known member
Aug 6, 2015
269
It seems a bit overkill to use Induction, when there's a simple rule for the Difference of Two Terms With the Same Power...

$\displaystyle \begin{align*} a^n - b^n \equiv \left( a - b \right) \sum_{r = 0}^{n - 1}{ a^{n - 1 - r}\,b^r } \end{align*}$

so in your case the factor would be (7 - 2) which equals 5.
Well, the school curriculum doesn't teach this rule, so yes, we were supposed to solve it with the "overkill" method.
 

Prove It

Well-known member
MHB Math Helper
Jan 26, 2012
1,403
Well, the school curriculum doesn't teach this rule, so yes, we were supposed to solve it with the "overkill" method.
Then you can consider it as something new that you have learnt. The most concise method of proof is always the best.