Induction is very closely related to a recursively-defined function (which are very useful in computer science). You may want to practice languages which rely on recursion (Scheme, Ocaml, Haskell, Erlang), as they may help you understand the process a little better.
Let's work with the example: P(n) is the statement 1 + 2 + 3 + ... + n = n(n+1) / 2. P is a predicate of one variable. Predicates are functions which can be true or false.
P(0) is 0 = 0(0+1) / 2, which is true.
P(1) is 1 = 1 * (1 + 1) / 2, which is also true.
P(2) is 1 + 2 = 2 * (2 + 1) / 2, which is also true.
P(3) is 1 + 2 + 3 = 3 * (3 + 1) / 2, which is still true.
We can check by hand if any given P(n) is true. It's really easy. You just plug in the value for n and plug it into your calculator. So for any individual n, finding out if P(n) is true is a simple matter of computation.
The problem is how do we show that no matter what n we choose, P(n) is a true statement? To calculate it by hand, we'd need to do an infinite number of computations. An important property of proofs is they must be finite! So how can we show, in a finite number of steps, P(n) is true?
The answer is we must assume an axiom of induction. This axiom goes like this:
If you can prove that P(0) is true and if for any n, we can show that P(n) being true implies that P(n+1) is true, then we can conclude for all n, P(n) is true.
Why do we accept this axiom as a legitimate part of logic? Well, if the two conditions are met (P(0) is true and P(n) implies P(n+1)), then we can recurse.
P(0) is true (base case)
P(0+1) = P(1) is true (by the implication)
P(1+1) = P(2) is true (by the implication)
P(2+1) = P(3) is true (by the implication)
... (and so on as high as we want)
So what I've outlined above is intuitively why induction is a legitimate form of proof. It's easy for most students to accept that, because they get graded on their proofs, not one whether or not they understand their proofs!
But the basic idea is simple. You need to prove your base case and the implication. The base case is always really easy, since it's a matter of computation. P(0). Plug in 0 for n in the formula and see if it's true or not.
The hard part is the implication step, because implication is really unintuitive! What does it mean that "P(n) implies P(n+1)"? It means assuming P(n) is true, proving that P(n+1) is true.
The confusion comes from that assumption. "If you *assume* P(n) is true, then aren't you assuming your entire proof is correct?" The answer is 'no'.
Douglas Hofstadter in his marvelous book Godel Escher Bach (GEB) describes the idea of logical implication very cleanly. He uses the term "fantasy" to give emphasis that your assumptions are just that! "Imagine a fantastic world where we found a magical number called n that made the statement P(n) true! What would the far reaching consequences of such a world be?"
Well, in the scenario above, let's assume some fantastic number n exists such that:
1 + 2 + ... + n = n (n+1) / 2.
What of it?
Well, by using regular logic inside of this fantasy world, we can deduce another fact:
1 + 2 + ... + n + (n+1) = n (n+1) / 2 + (n+1).... add (n+1) to both sides
1 + 2 + ... + n + (n+1) = (n (n+1) + 2(n+1) )/ 2.... do a little algebra to get a common 2 in the demoninator
1 + 2 + ... + n + (n+1) = (n^2 + 3n + 2 )/ 2.... more algebra.... multiply out the top
1 + 2 + ... + n + (n+1) = (n+1) (n+2) / 2... factor the top
1 + 2 + ... + n + (n+1) = (n+1) ((n+1) +1) / 2... do a final tweak to emphasize the form of the equation
If you are very astute (or have done induction before), you might notice that that last line is actually the statement P(n+1). The fantasy is over. By making your crazy assumptions, you have shown you can produce crazy results. After this step, you are *not* assuming P(n) is true. You have done your damage.
But what does this amount to? In order for this assumption to be any good, we'd need to actually find a suitable fantastic value for n. That's what the base case is for! The base case proves the existence of that n. Since P(0) is true, we can "invoke" our implication step. Let n=0, and our implication is P(0) => P(1). Since P(0) is true, then we conclude that P(1) is true. And since P(1) is true, we can invoke the implication step again, and prove P(2) is true. And when we are ready to turn in our test, we simply invoke the induction axiom above and conclude that "For all n, P(n) is true".
As you can hopefully see from this example, the hardest part of induction is understanding what "P(n) => P(n+1)" means and understanding how you prove it. There is also a lot of algebra during that step, which can be challenging as well (factoring polynomials is a bitch). Also, when real mathematicians do real proofs, they rarely figure the steps out in the order they appear in the proof. Human reasoning is very sketchy and the important steps will become obvious in a horrible messy way. Working backwards is often easier than working forwards, but your professor will expect the answer to be written forwards!