# Proof by mathematical Induction: Divisibility

1. Oct 23, 2005

### DeathKnight

The question is: Prove by mathematical Induction that
$$f(n) \equiv 2^{6n}+3^{2n-2}$$ is divisible by 5. This is what I did:
Suppose that the given statement is true for $$n=k$$
Since the$$f(k)$$ is divisible by 5,
$$f(k)=5A$$ (where A are is a constant.)
Also, from the given statement:
$$f(k)=2^{6k}+3^{2k-2}$$
To prove that the given statement is also true for n=k+1:
$$f(k+1)-f(k)$$
$$=2^{6k+6}+3^{2k} - (2^{6k}+3^{2k-2})$$
$$=2^{6k}(63)+3^{2k-2}(8)$$
After this I'm stuck! I know that I have to write it in the form of $$5B$$(where B is a constant) but I cant. This is because if I do take 5 common I get fractions in the above expression.
Thanks in advance for any help.

Last edited: Oct 23, 2005
2. Oct 23, 2005

### Benny

You should really start with a specific case. The statement is true for n = 1 since 2^6 + 3^0 = 65 is divisible by 5.
I find that the easiest approach for this problems is to start with the "n+1" expression where you replace n by n+1 and manipulate the expression to get it into the appropriate form.
$$f\left( {n + 1} \right) = 2^{6n + 6} + 3^{2n}$$

We want something with 2^6n or 3^(2n-2). The former is clearly the easier of the two to incorporate into the above expression so try to get that in there first.
$$= 2^6 \left( {2^{6n} } \right) + 3^{2n}$$

But you don't just want 2^6n in there somewhere do you? You'd much prefer to have 2^6n + 3^(2n-6) in there as well. So just add a 3^(2n-6) in the parenthesis with the 2^6n. Of course now you'll need to substract the relevant expression to maintain equality. From there it's just algebra, as with many questions of this type.

Last edited: Oct 23, 2005
3. Oct 24, 2005

### ivybond

You are almost there!
Benny is suggesting to use a very powerful solving technique: compare where you are to what result you need to get, and think of what would be nice to have as a stepping stone to close a gap.
Benny's solution mght be a little shorter, but since you've already come close to solution, let's continue.
Borrowing Benny's expression, you'd much prefer to see
$$2^{6k}+3^{2k-2}$$ in your
$$2^{6k}(63)+3^{2k-2}(8)$$.
Maybe, $$c(2^{6k}+3^{2k-2})$$, where c is a constant?
Say, $$c=63$$ (why?).
$$63(2^{6k}+3^{2k-2})=2^{6k}(63)+3^{2k-2}(63)$$.
It's not your $$2^{6k}(63)+3^{2k-2}(8)$$ yet, but you can make some adjustments.
$$f(k+1)-f(k)=63(2^{6k}+3^{2k-2})-?=63(5A)-?=5B$$

Now, I am not sure why you started with
$$f(k+1)-f(k)$$.
You could:
$$f(k+1)=2^{6k+6}+3^{2k}=2^{6k}(64)+3^{2k-2}(9)= 64(2^{6k}+3^{2k-2}) - ? = 64(5A) - ? = 5B$$

Last edited: Oct 24, 2005
4. Nov 5, 2007

### lawbrobbs

Good day sir's , ireally want to understand the mathematical induction in your site.I really need your help to accomplish my course for four years.I hope my request wont be denied.Thank you very much