Mathematical Induction Vol.I

Jai Ganesh · 2007-10-11 05:26:56

1. For any natural number n, prove that
5^(2n)-6n+8
is divisible by 9.

2. If n is any odd positive integer, prove that
n(n²-1) is divisible by 24.

3. Prove that
1²+2²+3²+4²+5²+.....n²=[n(n+1)(2n+1)]/6.

4. Prove that
1²+3²+5²+7²+9²+....(2n-1)²=[n(4n²-1)]/3.

5. Prove that (a^n-b^n) is divisible by (a-b).

6. Prove that 2^n>n³ if n>9.

7. Prove that
5^(2n)-6n+8 is divisible by 9 for all natural numbers n.

8. If p be a natural number, prove that
p^(n+1)+(p+1)^(2n-1) is divisible by
p²+p+1 for every positive integer n.

mikau · 2007-10-11 05:46:36

1. proof 5^(2n)-6n+8 is divisible by 9.

clearly for n = 1 we have 5^2 - 6 + 8 = 25 - 6 + 8 = 27 which is divisible by 9.

Suppose now by induction that 5^(2n)-6n+8 is dividible by 9, then
5^(2(n + 1)) - 6(n + 1) + 8 = (25)5^2n - 6n -6 + 8 =

(25)5^2n - 6n + 2 + 198 + 144n - 198 - 144n = 25(5^2n - 6n + 8) + 144n + 198. All three terms are divisible by 9 so the sum is divisible by 9. qed.

Last edited by mikau (2007-10-11 05:49:45)

Ricky · 2007-10-11 06:28:41

So if n is a volume Mathematical Induction, is n+1?

mikau · 2007-10-11 15:21:47

2. proof n(n²-1) is divisible by 24 for any odd integer n

base case, let n = 1, we have 1*0 = 0 which is divisible by 24. (zero counts, right?)

suppose now by induction that n(n²-1) is divisible by 24 where n is odd and positve. We must now show that (n+2)((n + 2)² - 1) is divisible by 24.
Observe that
(n+2)((n + 2)² - 1)= n(n²-1) + 6(n²-1) + 12(n+1).
the first term is divisible by 24 by the inductive hypothesis, for the second term, note that n is odd and n(n²-1) is divisible by 24, this means that (n^2 - 1) must contain a factor of 8. 6 contians a factor of 3 therefore 6(n²-1) is divisible by (3*8) or 24. In the last term, we know n is odd thus n+1 is even, hence it contains a factor of 2. so clearly 12(n+1) is divisible by (12*2) or 24. Each term is divisible by 24 therefore the sum is divisible by 24 and we are done.

Last edited by mikau (2007-10-11 15:23:56)

mikau · 2007-10-12 03:05:21

proof 1²+2²+3²+4²+5²+.....n²=[n(n+1)(2n+1)]/6.

blah! you're going to make me write all that out?

base case, n = 1, 1*2*3/6 = 1. Check!

assume its true for n, then we have

=[(n+1)(n+2)(2n+3)]/6, i'll play around with the numerator so i'll just drop the 6 for the moment

= 2n^3 + 9n^2 + 13n + 6

= n(2n^2 + 9n + 13) + 6

= n(2n^2 + 2n + 7n + 13) + 6

= n(2n(n+1) + 7n + 7) + 6 + 6n

= n(2n(n+1) + 7(n + 1)) + 6 + 6n

= n(n+1)(2n + 7) + 6 + 6n

= n(n+1)(2n + 1) + 6 + 6n + 6n(n+1)

= n(n+1)(2n + 1) + 6 + 6n + 6n^2+ 6n

= n(n+1)(2n + 1) + 6 + 12n + n^2

= n(n+1)(2n + 1) + 6(n+1)^2

bringing the denominator back from the grave, we get

n(n+1)(2n + 1)/6 + (n+1)^2 qed.

Last edited by mikau (2007-10-12 03:05:41)

mikau · 2007-10-12 05:19:16

hehe, how many more do i need to get a Ganesh award?

mikau · 2007-10-15 06:59:14

I'll skip 4 for now because its boring and laborious.

For 5 i came up with a proof thats unlike any other inductive proof i've done before in that it uses a double hypothesis. I came up with the idea as i found i needed to prove either of two things to complete the proof but i couldn't seem to prove 1 without the other. So i assumed by induction that both were true for k and proved both were true for k +1, take a look and tell me if its valid.

5. Proof that (a^k-b^k) is divisible by (a-b).

Suppose by induction that a^k - b^k is divisible by a - b, AND suppose ba^k - ab^k is divisible by a - b. (note the k's are the same)

for k = 1 or 2 it can be shown easily.

now observe that

a^(k+1) - b^(k+1) = (a - b)(a^k + b^k) + ba^k - ab^k the first term contains a factor of (a - b) and the second is divisible by our inductive hypothesis.

Now observe that

ba^(k+1) - ab^(k+1) = ab(a^k - b^k) which is also divisible by (a - b) by our inductive hypothesis.

It follows then that both (a^k-b^k) and ba^k - ab^k is divisible by (a-b) for all k.

Last edited by mikau (2007-10-15 07:01:41)

Kurre · 2007-10-26 10:49:11

2. if n=1 then n(n^2-1)=0 which is divisible by 24.
we also know that n(n^2-1)=n(n-1)(n+1)
Now we need to show that it is divisible with 24 for the next odd number, so we insert n+2 instead of n, which results in:
(n+2)(n+1)(n+3)
we now have two consecutive even numbers, which means that one of them is divisible with 2, and one with 4. These three numbers are also three consecutive numbers, which means that one of them is divisible with 3. 2*4*3=24

Last edited by Kurre (2007-10-26 20:45:21)

Kurre · 2007-10-26 21:41:00

4. induction base for 1: n(4*n²-1)/3=1(4*1-1)/3=1
now if we increase n with 1, the sum should increase with (2(n+1)-1)²=(2n+1)²

we replace n in n(4*n²-1)/3 with n+1:

(n+1)(4(n+1)²-1)/3= (n+1)(4n²+8n+4-1)/3=
( n(4n-1) + 8n²+4n+4n²+8n+4-1 )/3=
( n(4n-1) + 12n²+12n+3 )/3=
n(4n-1)/3 + 4n²+4n+1=
n(4n-1)/3 + (2n+1)²

keep posting these ganesh!

Last edited by Kurre (2007-10-26 21:41:28)

Math Is Fun Forum

#1 2007-10-11 05:26:56

Mathematical Induction Vol.I

#2 2007-10-11 05:46:36

Re: Mathematical Induction Vol.I

#3 2007-10-11 06:28:41

Re: Mathematical Induction Vol.I

#4 2007-10-11 15:21:47

Re: Mathematical Induction Vol.I

#5 2007-10-12 03:05:21

Re: Mathematical Induction Vol.I

#6 2007-10-12 05:19:16

Re: Mathematical Induction Vol.I

#7 2007-10-15 06:59:14

Re: Mathematical Induction Vol.I

#8 2007-10-26 10:49:11

Re: Mathematical Induction Vol.I

#9 2007-10-26 21:41:00

Re: Mathematical Induction Vol.I

Board footer