# Proof validation for number divisible by 25

• Mar 14th 2006, 04:49 AM
DenMac21
Proof validation for number divisible by 25
I have to prove that $2^{n + 2} \cdot 3^n + 5n - 4$ is divisible by $25$ for $n>0$.

My proof:
$\begin{array}{l}
2^{n + 2} \cdot 3^n + 5n - 4 = 2^n \cdot 2^2 \cdot 3^n + 5n - 4 = 6^n \cdot 4 + 5n - 4 = \\
5n - 4(6^n - 1) \\
\end{array}
$

This expression is divisible by 25 for $n=1$, so we look for $n>1$.

$6^n$ is always number which last two digits will be $36,16,96,76,56,36...$.
So we can establish now for which value of n will last two digits be for number $6^n$.

$k>0$
$\begin{array}{l}
n = 5k - 3,{\rm{ }}6^{5k - 3} = ....36 \\
n = 5k - 2,{\rm{ }}6^{5k - 2} = ....16 \\
n = 5k - 1,{\rm{ }}6^{5k - 1} = ....96 \\
n = 5k,{\rm{ }}6^{5k} = ....76 \\
n = 5k + 1,{\rm{ }}6^{5k + 1} = ....56 \\
\end{array}
$

Since we have expression $4(6^n - 1)$ then last two digits of that expression will be:

$\begin{array}{l}
n = 5k - 3,{\rm{ }}4(6^{5k - 3} - 1) = ....40 \\
n = 5k - 2,{\rm{ }}4(6^{5k - 2} - 1) = ....60 \\
n = 5k - 1,{\rm{ }}4(6^{5k - 1} - 1) = ....80 \\
n = 5k,{\rm{ }}4(6^{5k} - 1) = ....00 \\
n = 5k + 1,{\rm{ }}4(6^{5k + 1} - 1) = ....20 \\
\end{array}
$

If we now look at whole expression we will get:
$\begin{array}{l}
n = 5k - 3,{\rm{ }}5(5k - 3) - 4(6^{5k - 3} - 1) \\
n = 5k - 2,{\rm{ }}5(5k - 2) - 4(6^{5k - 2} - 1) \\
n = 5k - 1,{\rm{ }}5(5k - 1) - 4(6^{5k - 1} - 1) \\
n = 5k,{\rm{ }}5(5k) - 4(6^{5k} - 1) \\
n = 5k + 1,{\rm{ }}5(5k + 1) - 4(6^{5k + 1} - 1) \\
\end{array}
$

For example lets take first expression too see if its divisible by 25, same proof is for other ones.
$5(5k - 3) - 4(6^{5k - 3} - 1) = 25k - 15 - .....40$
.....40 means that last two digits of that number is 40. .....40 - 15 have last two digits 25, so we have number $25k + .....25$ which is divisible by 25. Same proof is for other numbers.

Is this proof valid?
• Mar 15th 2006, 08:42 PM
earboth
Quote:

Originally Posted by DenMac21
I have to prove that $2^{n + 2} \cdot 3^n + 5n - 4$ is divisible by $25$ for $n>0$.
...
Is this proof valid?

Hello,

your proof looks OK to me. When I did this proof for my own (pleasure, of course!) I came to the same result. Here is my way to do it:

I use "complete induction" (I'm quite certain, that this isn't the correct expression. It's litterally translated from German. Sorry!). You have to use Peano's Axiom about $\mathbb{N}$.

1. A(n=1): $2^{1 + 2} \cdot 3^1 + 5\cdot 1 - 4=24+1\ is\ divisible\ by\ 25$
2. A(n): Let $2^{n + 2} \cdot 3^n + 5\cdot n - 4\ is\ divisible\ by\ 25$ be true.
A(n+1): $2^{n+1 + 2} \cdot 3^n+1 + 5\cdot(n+ 1) - 4=$
$2\cdot 2^{n + 2} \cdot 3 \cdot 3^n + 5\cdot n+ 5 - 4=$
$6\cdot 2^{n + 2} \cdot 3^n + 5\cdot n+ 5 - 4=$
$5\cdot 2^{n + 2} \cdot 3^n +5+\underbrace{2^{n + 2} \cdot 3^n+5\cdot n - 4}_{\csub{div.\ by\ 25}}=$
$5\cdot \left(2^{n + 2} \cdot 3^n +1 \right)+\underbrace{2^{n + 2} \cdot 3^n+5\cdot n - 4}_{\csub{div.\ by\ 25,\ see \ A(n)}}=$
$5\cdot \left(4 \cdot 6^n +1 \right)+\underbrace{2^{n + 2} \cdot 3^n+5\cdot n - 4}_{\csub{div.\ by\ 25}}=$
All powrs of 6 have as last digit a 6, so the produkt 4*6^n has always a 4 as it's last digit. That means the number in the paranthesis has a 5 as last digit and is therefore divisible by 5. Therefore the 1rst summand is divisible by 25 too. Therefore the complete expression is divisible by 25.

Now you've proofed that your expression is true for (n+1) if it is true for n. That means: You've proofed, that it is true for n=1.
Because it is true for n=1 it is true for n=1+1=2 too;
because it is true for n=2 it is true for n=2+1=3 too;
because it is true for n=3 it is true for n=3+1=4 too.

So it is true for all $n \in \mathbb{N}$

Maybe this was of some help for you.

Greetings

EB
• Mar 16th 2006, 04:56 AM
CaptainBlack
Quote:

Originally Posted by earboth
Hello,

your proof looks OK to me. When I did this proof for my own (pleasure, of course!) I came to the same result. Here is my way to do it:

I use "complete induction" (I'm quite certain, that this isn't the correct expression. It's litterally translated from German. Sorry!). You have to use Peano's Axiom about $\mathbb{N}$.

1. A(n=1): $2^{1 + 2} \cdot 3^1 + 5\cdot 1 - 4=24+1\ is\ divisible\ by\ 25$
2. A(n): Let $2^{n + 2} \cdot 3^n + 5\cdot n - 4\ is\ divisible\ by\ 25$ be true.
A(n+1): $2^{n+1 + 2} \cdot 3^n+1 + 5\cdot(n+ 1) - 4=$
$2\cdot 2^{n + 2} \cdot 3 \cdot 3^n + 5\cdot n+ 5 - 4=$

Shorter route from here is:

Suppose A(n) is true then consider:

$2^{n+1 + 2}\ 3^{n+1} + 5(n+ 1) - 4=$
$(2^{n+2}\ 3^n + 5n -4)6 -30n + 24 +5(n+1) -4=$
$(2^{n+2}\ 3^n + 5n -4)6 -25n +25$

But the first term in the last line above is divisible by 25 by hypothesis, and
the second term is a multiple of 25, so A(n+1) holds, and so it follows
by mathematical induction that A(n) is true for all n in $\mathbb{N_+}$

I must admit that I had been putting off checking DenMac21's proof because
it looked too long and complicated :D

RonL
• Mar 16th 2006, 06:48 AM
DenMac21
Quote:

Originally Posted by CaptainBlack
Shorter route from here is:

Suppose A(n) is true then consider:

$2^{n+1 + 2}\ 3^{n+1} + 5(n+ 1) - 4=$
$(2^{n+2}\ 3^n + 5n -4)6 -30n + 24 +5(n+1) -4=$
$(2^{n+2}\ 3^n + 5n -4)6 -25n +25$

But the first term in the last line above is divisible by 25 by hypothesis, and
the second term is a multiple of 25, so A(n+1) holds, and so it follows
by mathematical induction that A(n) is true for all n in $\mathbb{N_+}$

I must admit that I had been putting off checking DenMac21's proof because
it looked too long and complicated :D

RonL

Ye, I admit it looks scary! :eek:

It is long, but its rather simple, I don' think its complicated.

I must say that I do not know the way of solution that earboth and you gave here.

"complete induction" , Peano's Axiom is not known to me! :confused:
• Mar 16th 2006, 07:18 AM
CaptainBlack
Quote:

Originally Posted by DenMac21
Ye, I admit it looks scary! :eek:

It is long, but its rather simple, I don' think its complicated.

I must say that I do not know the way of solution that earboth and you gave here.

"complete induction" , Peano's Axiom is not known to me! :confused:

It is bog standard Mathematical Induction, which is usually treated
as an axiom of arithmetic (probably it is one of Peano's axioms I
don't recall at this time)

RonL