Induction Made Easy: A Comprehensive Online Resource for Beginners

[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?

 

[matt grime]

Just try to do some examples. Follow the examples in your textbook.

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?

 

[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 I am not given a general formula. just the formula for the sequence how do i determine the General formula of the series?

 

[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

 

[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 I am asked to prove ((n^3)-n) is divisible by 6 for all n belongs to N by induction.

 

[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

 

[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.

The principle is that if a series it is true for any number n it is ALSO true for the number that follows n.

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

i solved the question above and got that k^2+3k+2==k^2+3k+2

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

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.

I do not understand that sentence.

and also what if I am not given a general formula. just the formula for the sequence how do i determine the General formula of the series?

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.

 

[matt grime]

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 I am asked to prove ((n^3)-n) is divisible by 6 for all n belongs to N by induction.

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?)

 

[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... that's 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?

 

[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.

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