Need Questions for a Exam coming up - Math Induction

Printable View

November 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

Thanks in advance for anyhelp

~Regards
Name101
November 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}$
November 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
November 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$
November 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
November 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.
November 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..)