[beeny]

Alright, time for a rant. I'm [censored] pissed at the grade I got from a problem set in my algorithms class... It also kinda pisses me off that they're making induction a big deal in this class when you should have learned it in discrete math? Anyway, give me your opinions on what I should have gotten (out of 7). This is what I wrote:

***START***

For n > 2, let F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1.
I will show that for n > 1 F(n) > .01(3/2)^n using induction.

Base case:
n = 1. F(1) = 1 > .01(3/2)^1 = .015
n = 2. F(2) = F(1) + F(0) = 1 + 0 > .01(3/2)^2

Inductive Hypothesis: Assume F(n) > .01(3/2)^n and F(n-1) > .01(3/2)^(n-1)

Using the inductive hypothesis, we will show that F(n+1) > .01(3/2)^(n+1)

F(n+1) = F(n) + F(n-1) > .01(3/2)^n + .01(3/2)^(n-1) = .01(3/2)(3/2)^(n-1) + .01(3/2)^(n-1) = .01(3/2 + 1)(3/2)^(n-1) = .01(5/2)(3/2)^(n-1) > .01(9/4)(3/2)^(n-1) = .01(3/2)^(n+1) (Ok, this part there may be a few typos (hopefully not!) but this part was correct, even the professor I'm bitching about agreed!)

So, F(n+1) > .01(3/2)^(n+1)

***END***

So, how many points would you give me (out of 7)? Prof gave me 4/7



Basically, the professor's complaint was this:

First, off I have to define a P(n). So he wanted me to clearly state P(n) = F(N) > .01(3/2)^n. From this, use induction on P(n). This whole step isn't necessary (I'm pretty sure) in doing induction. It just helps you save some steps, and things are just clearer. Basically think of it as saying x = messy equation, and if you just state once that x = messy equation, then you can state x afterwards instead of the messy equation all the time...

Second, he didn't like my inductive hypothesis. Assuming I defined P(n) (which is what he wanted) he wanted me to state the inductive hypothesis as such: "Assume P(1) and P(2) and ... and P(n-1) and P(n)". As far as I know, for induction, assuming only P(n) is enough. For this particular problem though I'm pretty sure assuming P(n-1) and P(n) is necessary and sufficient (granted I wrote it out the long way and assumed F(n) > .01(3/2)^n and F(n-1) > .01(3/2)^(n-1), that is instead of using the whole P(n) [censored])

Third, he wants all inductive proofs to end with "P(1) and .... and P(n) => P(n+1), and this holds for all n. By proof of induction for all n > 1, P(n). Q.E.D." He pretty much wants that word for word written at the end of all induction proofs. He actually even said, as long as you wrote that down, you will get 1 or 2 points.

Anyway, I personally think most of what he said was bullcrap, what are your thoughts?