Need help with the following questions.
Thank you guys so much!
Well, I don't know where to begin for all three questions. In my worksheet these are the only 3 Mathematical Induction questions, and I was sick the day they went through this and didn't attend class. :/
let's work through number 3 in some detail, and perhaps you can try the other two on your own.
first, this is how a proof by induction works:
we prove that a formula works for some "starting number" (usually 0 or 1, but not always).
then we prove that IF (and this is a big if) it works for "some number", then it will always work "for the next number".
well, since we know it works for the starting number (let's call it "a"), then the "one to the next" part of the proof means it works for:
a+1, (a+1)+1 = a+2, (a+2)+1 = a+3,.....,and so on (think of a string of dominoes, here).
in short, it works for a, and every number after a.
ok, now let's see a real-live induction proof in action. first, we state what we intend to prove:
ok, so "r" is just a dummy variable here (an INDEX), so that we don't have to write "....." in a really long sum. so we are going to use induction on "n" (that is, prove this is true for every integer n larger than or equal to 1).
so, our starting number (or what is referred to as "the base case") will be in this instance, n = 1. so, we have to prove that our formula is correct when n = 1.
. that's the left-hand side (or LHS, as mathematicians are wont to write). now the RHS:
for n = 1, this is: .
this shows that our formula works for n = 1. that's good
now here is the point at which most people get confused. what we are about to do almost seems like cheating. we are going to ASSUME:
(even though the only "n" we know for sure works at this point is n = 1),
and then we are going to PROVE that, given our assumption (or "induction hypothesis"):
. note all that has changed is we replaced "n" in our formula with "n+1".
of course, if this works, then true for n = 1, will imply true for n = 2. and THEN, true for n = 2, will imply true for n = 3. and THEN....
(this will save us the trouble of checking each case individually, which is GOOD, since there's an infinite number of positive integers, and i can't count that high).
so, let's get to it: first note we can split the LHS side like so:
now the first term on the right side can be replaced (by our assumption), with:
. so we have:
.
now, we need to do some, ugh, algebra, to see if we can clean this up a little:
(whew! i need to take a lil break after all that work!). ok, so let's march on:
, which is the formula for "n+1".
so we proved the formula true for "n" implies the formula is true for "n+1", in which case it holds for EVERY integer greater than or equal to 1.