MathDoofus wrote:Gotcha. How do I know when I've correctly derived the k + 1 case (the then) from the k case (the if)?
Start withleft_side(k) = right_side(k)
You know this is true for at least one k. (That was your first step.)
Now writeleft_side(k+1) =? right_side(k+1)
You don't know this is true yet. The object is to get this to look like what you started with. Bit by bit you get the left side to look like it's earlier form, while doing exactly the same thing to the right side (to maintain the supposed equality). When simplified, the right side should comply also, and you'll be there.
If you do correct algebra, and you mange to get your first equation back, you've done it.
Hint: The second-to-last stage will probably look something
likeleft_side(k) + 1 =? right_side(k) + 1
and subtracting 1 from both sides gets you home. What it actually
looks like depends on the equations involved.
Then, you can replace the =? in that last step with = (because you know the last step is true).... and working backwards you know the previous steps must have also been true. You end up replacing =? with = in the beginning, and add a Latin TLA at the end.
I have come back to this over the holidays, and I'm happy to report that some of everyone's advice has sunk in. Below is my understanding of the example problem.
Prove P(n): 1 + 2 + 3 + ... + n = [n(n + 1)]/2
First, I'll try a base case to be sure that it works for some n. I'll use 1 as the base case because it seems to be the simplest.
Base case checks out: 1 = [1(1 + 1)/2
1 = [1(2)]/2
1 = 1
Next, I'll assume that the k case is true.
The k case looks like this: P(k): 1 + 2 + 3 + ... + k = [k(k + 1)]/2
And I'll use the conditional (i.e., if x, then y) to see if the (k + 1) case is true if the k case is true. To do that, I'll replace all references to k on the right-hand side with (k + 1).
1 + 2 + 3 + ... + k + (k + 1) = (k + 1)[(k + 1) + 1]/2
The insight is that, because I'm using a conditional, I can replace much of the stuff on the left-hand side with the right-hand side of the k case.
[k(k + 1)]/2 + (k + 1) = (k + 1)[(k + 1) + 1]/2
My next goal is to try to make the left-hand side identical to the right-hand side. Although my algebra knowledge is incomplete and rusty, here's what I've come up with (I do remember the FOIL rule).
[k(k + 1)]/2 + [2(k + 1)]/2 = [(k + 1)(k + 2)]/2 ***I've given everything a common denominator***
[k(k + 1) + 2(k + 1)]/2 = [(k + 1)(k + 2)/2] ***I've simplified on the left-hand side***
(k^2 + k + 2k + 2)/2 = [(k + 1)(k + 2)]/2 ***Continuing to work on the left-hand side***
(k^2 + 3k + 2)/2 = [(k + 1)(k +2)]/2 ***Continuing to work on the left-hand side***
(k^2 + 3k + 2)/2 = (k^2 + 2k + k + 2)/2 ***Applied FOIL to the right-hand side***
(k^2 + 3k + 2)/2 = (k^2 + 3k + 2)/2 ***Left-hand side and right-hand side are now identical, so I've shown that if the k case is true, then the (k + 1) case is true. And because I've already checked a base case (and because of the well-ordering principle), I've shown that it's true for all values of n.
Is the above correct?