# Resource on induction

1. Aug 28, 2006

### yourmom98

i am totally lost on this subject. like i have NO CLUE what its about or what to do or how to prove things. Can anyone recommend a good site or online resource about this induction stuff?

2. Aug 29, 2006

### matt grime

Just try to do some examples. Follow the examples in your text book.

Can you state the principlee behind induction? What is it? Now, take this example:

show for all n greater than or equal to one that 1+2+3+..+n=n(n+1)/2

and prove it using induction. What is the base case? Assume it is true for some value of n, say n=k. Can you *using this assumption* prove it true when n=k+1?

3. Aug 29, 2006

### yourmom98

The principle is that if a series it is true for any number n it is ALSO true for the number that follows n. i solved the question above and got that k^2+3k+2==k^2+3k+2 therefore i proved this series. however the sequence is not always that easy as it it just equals n how do i find the nth term then. and also what if im not given a general formula. just the formula for the sequence how do i determine the General formula of the series?

4. Aug 29, 2006

### island-boy

in induction, you have to prove 2 things
1) that the equation is true for n=1
2) that the equation is true for n= k+1 GIVEN that it is true of n = k.
usually, the difficulty lies in the second.
You need to use the equation created when n = k, manipulate it somehow (the hard part), and make it true for the case when n =k+1.
There is no easy way to do the second part. Usually, different methods apply for different cases. Just try to get as much practice with doing some sample problems, so at least you'll be comfortable doing it.
hope that helps

5. Aug 29, 2006

### yourmom98

im starting to get the hang of that now. however i have problems when trying to get the General formula of the series from the formula of the sequence. a example is that im asked to prove ((n^3)-n) is divisible by 6 for all n belongs to N by induction.

6. Aug 29, 2006

### island-boy

the trivial case is easy.

for the case for n = k+1, try to substitue n with both k+1 and k, and manipulate (try factorization) both equations, knowing that the case when n = k is considered true

7. Aug 29, 2006

### matt grime

I'm going to get a bit nit-picky, but one of the main reasons people go wrong with maths is because they don't take care with their work, and don't have things straight in their own mind.

What does 'it' refer to? What series? A series is not a statement that is true or false, it is just a series.

how did you do this? tell us, so we have a better idea of what you are doing.

I do not understand that sentence.

How you determine something will depend on what the something is. There isn't a universal rule for doing maths problem (beyond sit and think about it for a while and elightenment will dawn, hopefully).

You didn't state the general principle of induction, by the way. That was the main thing I need you to write out properly so that we can tell what you think is going on. You almost posted it, but that wasn't the general principle of induction, and omits at least one important thing. Further, not all induction questions are to do with series.

8. Aug 29, 2006

### matt grime

Suppose it is true for n=k, and consider the statement for n=k+1 (as always). Now, how can I take

(k+1)^3 - (k+1) (*)

and get something involving k^3 - k?

There is only one thing you can do with (*) so do it (that is expand the bracket), and then see what you have left over.

(Hint: if a number, X divides both Y and Z it divides what else?)

9. Aug 29, 2006

### yourmom98

In your first post. I should check my posts more carefully. The principle is that the general equation of a series is correct if it works for a number n and is n+1

i got k^2+k+2k+2=k^2+k+2k+2 by subbing in k=n into n(n+1)/2 and then taking that and subbing that into the sequence of k+1=n and simplifying the left and right sides to see if they are equal. they were therefore the equation was proven. and the 3rd thing i figured that part out. and yea more proof reading needed. hmm..... thats all i know about induction. what important thing did i omit?

In your second post. what does the * represent? and if a number X divides both Y and Z it also divides YZ? hmmm..... i know what to do now. I factored n^3-n and got (n)(n+1)(n-1) and realized that they were 3 consecutive integers. So now with that hint i can state that since (n)(n+1)(n-1) is divisible by 6 it must also be divisible by 2 and 3. Therefore logically since there are 3 consecutive numbers one has to be even therefore divisible by 2 and since there are 3 numbers one of those 3 numbers has to be divisible by 3. therefore ((n^3)-n) has to be divisible by 6. but... is this solving by induction?

10. Sep 3, 2006

### CSE Student

No I don’t think that is induction. I am stuck with the same problem but I figured it out while I was making this post. My computations are as follows:

Question:
prove n^3 - n is divisible by 6 for all n's that are natural numbers

My Attempt:

Step 1) Base Case:: n = 2

(I chose this as the base case because n = 1 results in 0 and so does 0, and although 0/6 is 0 with remainder 0, I didn’t think this was useful information.)

Step 2) Induction Hyp#1:: n = k; k ^ 3 - k is divisible by 6

(2)^3 - 2 = 6; 6 is divisible by 6 so the base case works.

Step 3) If I can show that (k + 1) ^ 3 - (k +1) is divisible by 6 then I will have solved the problem.

(k + 1) ^ 3 - (k +1) expanding this yields
(k + 1) (k + 1) (k + 1) - (k +1)
k ^3 + 3k^2 + 3k + 1 - k - 1 rearranging the expression yields

k^ 3 - k + 3k^2 + 3k + 1 - 1 by the induction hypothesis k^3 - k is divisible by 6 and the 1's cancel so all that is left is the rest of the equation...

3k^2 +3k I attempt further induction on what's left...

Step 4) Base case #2:: k = 1
Step 5) Induction Hyp #2::
k = x
3(x)^2 + 3(x) is divisible by 6
3(1)^2 + 3(1) = 6; 6 is divisible by itself so the base case works...

Step 6) If I can show that

3(x + 1)^2 + 3(x+1) results in a number divisible by 6 then I am done expanding the expression results in
3x^2 + 9x + 6 the answer was revealed to me after staring at this expression for hours similar to those 3D illusions. :surprised

My final hint is that it uses the 2nd induction hyp. like in the first half of the problem. A helpful site on induction is http://www.cpax.org.uk/maths/induction.php

Last edited by a moderator: Apr 22, 2017