Proof of divisibility by induction method.

[Sonal7]

Prove that 2⁽⁵ⁿ⁺¹⁾+5⁽ⁿ⁺²⁾is divisible by 27 for any integer n.

We proceed by induction.
base case is 0
=[MATH]2+5^2=27[/MATH]Therefore true for n=0.
Consider n+1
2^5(n+1)+5+5^(n+1)+2

=2⁵ⁿ⁺⁶+5ⁿ⁺³
=2⁵x2⁵ⁿ⁺¹+5x5ⁿ⁺²
I dont know what to do next, I know that 32-5 is 27. but how do i got about subtracting those two as they are not the same type. I hope you understand what I mean. I always get stuck at this stage.

 

[Dr.Peterson]

Prove that 2⁽⁵ⁿ⁺¹⁾+5⁽ⁿ⁺²⁾is divisible by 27 for any integer n.

We proceed by induction.
base case is 0
=[MATH]2+5^2=27[/MATH]Therefore true for n=0.
Consider n+1
2^5(n+1)+5+5^(n+1)+2

=2⁵ⁿ⁺⁶+5ⁿ⁺³
=2⁵x2⁵ⁿ⁺¹+5x5ⁿ⁺²
I dont know what to do next, I know that 32-5 is 27. but how do i got about subtracting those two as they are not the same type. I hope you understand what I mean. I always get stuck at this stage.

You want to express 2⁵x2⁵ⁿ⁺¹+5x5ⁿ⁺² using 2⁵ⁿ⁺¹+5ⁿ⁺².

How about starting with 2⁵x(2⁵ⁿ⁺¹+5ⁿ⁺²), which you know is a multiple of 27, and seeing what has to be added or subtracted to reach the goal. Maybe you have to add or subtract something that is a multiple of 27.

Often in these problems you try something and hope! (You'll find, in this case, that you already have the main idea!)

 

[pka]

\(2^{5n+6}+5^{n+3}=\\2\cdot 2^{5n+5}+5^3\cdot 5^{n}\\2^6\cdot 2^{5n}+5^3\cdot 5^{n}\\2^6\cdot 2^{5n}+2^5\cdot 5^{2}\cdot 5^n-2^5\cdot 5^{2}\cdot 5^n+5^3\cdot 5^{n}\\2^5(2^{5n+1}+5^{n+2})-5^2\cdot 5^n(2^5-5)\)

 

[Dr.Peterson]

To demonstrate my way of discovering the answer, we have

[MATH]2^{5n+6} + 5^{n+3} = 2^{5n+6} + 5\cdot5^{n+2}[/MATH],​

and we compare it to the known multiple of 27 that has the right first term,

[MATH]2^5(2^{5n+1} + 5^{n+2}) = 2^{5n+6} + 32\cdot 5^{n+2}[/MATH];​

the difference between these is

[MATH](5-32)\cdot5^{n+2} = -27\cdot5^{n+2}[/MATH].​

So we just have to add this:

[MATH](2^{5n+6} + 5^{n+3}) = 2^5(2^{5n+1} + 5^{n+2}) - 27\cdot5^{n+2}[/MATH],​

which is a multiple of 27. Having discovered this, we can show that these are equal in a more direct way in our actual proof.

 

[Sonal7]

Heres a trick they used. I could not understand their method at first but this also works.

As you assume true for n.

You assume that 2⁽⁵ⁿ⁺¹⁾+5⁽ⁿ⁺²⁾(mod 27)=0 as is divisible by 27 for any integer n.

you can write 2⁽⁵ⁿ⁺¹⁾+5⁽ⁿ⁺²⁾(mod 27)=0, for any integer n.

One might rearrange this equation to:
5⁽ⁿ⁺²⁾(mod 27) =-2⁽⁵ⁿ⁺¹⁾ (one of the laws of mod arithmetic)

They have cunningly sub in this in this:
=2⁵x2⁵ⁿ⁺¹+5x5⁽ⁿ⁺²⁾(Mod 27)

This gives a form where all the bases are 2.

=2⁵x2⁵ⁿ⁺¹-5x2⁽ⁿ⁺²⁾

I love this question, this is actually genius from my perspective.

 

[Dr.Peterson]

It took me a while to understand what you are saying, in part because of a typo on the last line. You meant =2⁵*2⁵ⁿ⁺¹-5*2⁽⁵ⁿ⁺¹⁾ = 27 *2⁽⁵ⁿ⁺¹⁾ = 0 (mod 27).

This is a nice approach, working in mod 27. I didn't consider using modular arithmetic, in part because I didn't know whether you are familiar with it, and also because the context didn't suggest it. In a way, it can be described as equivalent to what I did.

 

[lookagain]

Compare that the problem wanted the induction method with this direct approach:

Prove that \(\displaystyle \ \ 2^{5n + 1} \ + \ 5^{n + 2} \ \ \) is divisible by 27 for any positive integer n.

\(\displaystyle 2^{5n + 1} \ + \ 5^{n + 2} \ = \)

\(\displaystyle 2^{5n}\cdot2^1 \ + \ 5^n\cdot5^2 \ = \)

\(\displaystyle 32^n\cdot 2^1 \ + \ 25\cdot 5^n \ = \)

\(\displaystyle (27 + 5)^n\cdot 2^1 \ + \ (27 - 2)\cdot 5^n \ = \)

\(\displaystyle [27^n \ + \ n(27)^{n-1}(5)^1 \ + \ ... \ + \ n(27)^1(5)^{n-1} \ + \ 5^n]\cdot2 \ + \ 27(5)^n \ - \ 2(5)^n \ = \)

\(\displaystyle [27^n \ + \ n(27)^{n-1}(5)^1 \ + \ ... \ + \ n(27)^1(5)^{n-1}]\cdot2 \ + \ (5)^n\cdot 2 \ + \ 27(5)^n \ - \ 2(5)^n \ = \)

\(\displaystyle [27^n \ + \ n(27)^{n-1}(5)^1 \ + \ ... \ + \ n(27)^1(5)^{n-1}]\cdot2 \ + \ 27(5)^n \ + \ 2(5)^n \ - \ 2(5)^n \ = \)

\(\displaystyle [27^n \ + \ n(27)^{n-1}(5)^1 \ + \ ... \ + \ n(27)^1(5)^{n-1}]\cdot2 \ + \ 27(5)^n \ = \)

\(\displaystyle 27\{[27^{n - 1} \ + \ n(27)^{n - 2}(5)^1 \ + \ ... \ + \ n(27)^0(5)^{n-1}]\cdot2 \ + \ 27^0(5)^n\} \ = \)

\(\displaystyle 27\{[27^{n - 1} \ + \ n(27)^{n - 2}(5) \ + \ ... \ + \ n(5)^{n-1}]\cdot2 \ + \ (5)^n\} \)

 

[pka]

Here is the above but using a different notation,
\(\begin{gathered}
{2^{5n + 1}} + {5^{n + 2}} = 2 \cdot {({2^5})^n} + 25 \cdot {5^n} = 2 \cdot {(32)^n} + 25 \cdot {5^n} \hfill \\
= 2 \cdot {(27 + 5)^n} + 25 \cdot {5^n} = 2\sum\limits_{k = 0}^n {\dbinom{n}{k}{{(27)}^k}{{(5)}^{n - k}}} + 25 \cdot {5^n} \hfill \\
= 2\sum\limits_{k = 1}^n {\dbinom{n}{k}{{(27)}^k}{{(5)}^{n - k}}} + 2 \cdot {5^n} + 25 \cdot {5^n}\text{ note the change of index. } \hfill \\
= 2\sum\limits_{k = 1}^n {\dbinom{n}{k}{{(27)}^k}{{(5)}^{n - k}}} + {5^n}(2 + 25) \hfill \\ \end{gathered} \)
Please note that the last line is clearly a multiple of twenty-seven. Thus as Lookagain observes this proof does not need induction.
My reply #3 gives the proof of the inductive step.