# Need Questions for a Exam coming up - Math Induction

• Nov 24th 2007, 05:44 PM
name101
Need Questions for a Exam coming up - Math Induction
Hello, And thanks for coming to have a look in here.
I'm in need of some study questions for mathimatical induction because my current issue of the text book does not have that chapter in there.

So all im asking is could someone or a group, give me some questions on mathimatical induction ranging from easy to harder (I need to rememeber how to do them :( )

I'll post up my answers and then they can be marked :p

~Regards
Name101
• Nov 24th 2007, 08:43 PM
Soroban
Hello, name101!

Here are some basic problems to get you warmed up . . .

$1 + 2 + 3 + \cdots + n \;=\;\frac{n(n+1)}{2}$

$1 + 3 + 5 + \cdots + (2n-1) \;=\;n^2$

$1^2 + 2^2 + 3^2 +\cdots + n^2 \;=\;\frac{n(n+1)(2n+1)}{6}$

• Nov 25th 2007, 12:36 AM
name101
Oh thank you
ok here we go.

Question 1:
$1 + 2 + 3 +...+n = \frac{n(n+1)}{2}$

after a few lines of working.
assuming n=k is true.

prove for n=(k+1)
$\frac {k(k+1)}{2}+(k+1)=\frac {(k+1)(k+1+1)}{2}$

$(k+1)(k+2) = (k+1)(k+2)$

Question 2:

$1 + 3 + 5+...+(2n-1) = n^2$

test for n = 1

$(2\times n +1)=n^2$

$1 = 1$

assume true for n=k

prove for n=k+1

$k^2+(2(k+1)+1) = (k+1)^2$

$(k+1)^2= (k+1)^2$

Question 3:

$1^2+2^2+3^2+...+n^2=\frac {n(n+1)(2n+1)}{6}$

test for n=1
$1^2 = \frac {1 \times 2 \times 3}{6}$

$1 = 1$

assume true for n=k

prove for n=k+1

$\frac {k(k+1)(2k+1)}{6} + (k+1)^2 = \frac {(k+1)(k+2)(2(k+1)+1)}{6}$

$LHS = RHS = 2k^3 + 9k^2 + 3k +6$

I think there Right :D
thanks for those if they are incorrect please point out. but I think I nailed them.
some more questions a little harder please.

~Regards
Name101
• Nov 25th 2007, 12:57 AM
kalagota
here are some..

a) 4 divides $5^n - 1$

b) $\sum_{k=1}^n k = \frac{[n(n+1)]}{2}$

c) $4^n > n^4$ if $n \geq 5$

d) $1+2+4+ ... + 2^{n-1} = 2^n - 1$

e) do you know tower of hanoi? show that the minimum moves required to transfer n-disks from one peg to another is $2^n - 1$
• Nov 25th 2007, 02:42 AM
CaptainBlack
Quote:

Originally Posted by name101
ok here we go.

Question 1:
$1 + 2 + 3 +...+n = \frac{n(n+1)}{2}$

after a few lines of working.
assuming n=k is true.

prove for n=(k+1)
$\frac {k(k+1)}{2}+(k+1)=\frac {(k+1)(k+1+1)}{2}$

$(k+1)(k+2) = (k+1)(k+2)$

Question 2:

$1 + 3 + 5+...+(2n-1) = n^2$

test for n = 1

$(2\times n +1)=n^2$

$1 = 1$

assume true for n=k

prove for n=k+1

$k^2+(2(k+1)+1) = (k+1)^2$

$(k+1)^2= (k+1)^2$

Question 3:

$1^2+2^2+3^2+...+n^2=\frac {n(n+1)(2n+1)}{6}$

test for n=1
$1^2 = \frac {1 \times 2 \times 3}{6}$

$1 = 1$

assume true for n=k

prove for n=k+1

$\frac {k(k+1)(2k+1)}{6} + (k+1)^2 = \frac {(k+1)(k+2)(2(k+1)+1)}{6}$

$LHS = RHS = 2k^3 + 9k^2 + 3k +6$

I think there Right :D
thanks for those if they are incorrect please point out. but I think I nailed them.
some more questions a little harder please.

~Regards
Name101

You need to put more description of what you are doing and what you havedone in these.

RonL
• Nov 25th 2007, 03:03 AM
name101
@ Cap't Black:
Ah, yes sorry. This was taking a lot longer than I thought to re-write my answers from the book and I was limited in time.( I had work to go to.)

Also another Question. how would I write my final statement at the end of the questions? to sum the question up.

@kalagota:

"tower of hanoi?"
mm never heard of these being called this name before.did a quick wiki search and found what they are to find I created one in wood work 5 years ago with no understanding of were it's origin was or name :D

I will post full working tomorrow night of the new questions I have recived.
For now im off to bed.

Thanks.
• Nov 25th 2007, 03:43 AM
kalagota
Quote:

Originally Posted by name101
@ Cap't Black:
Ah, yes sorry. This was taking a lot longer than I thought to re-write my answers from the book and I was limited in time.( I had work to go to.)

Also another Question. how would I write my final statement at the end of the questions? to sum the question up.

personally, i rewrite the statements and add "is true for all natural number n."

Quote:

Originally Posted by name101
@kalagota:

"tower of hanoi?"
mm never heard of these being called this name before.did a quick wiki search and found what they are to find I created one in wood work 5 years ago with no understanding of were it's origin was or name :D

I will post full working tomorrow night of the new questions I have recived.
For now im off to bed.

Thanks.

Tower of Hanoi -- from Wolfram MathWorld

they didn't give the inductive proof, try to understand how the puzzle works and then you can show that the formula is true.. Ü (but in case, i'll describe how the puzzle works..)