How to use induction

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

[sirio11]

As a professor who has thought induction before, I'll give you the 7 points, 6 at the worse, being picky. Don't really understand the 4, sounds retarded to me.

[TomCowley]

This might not be a 7 if the professor woke up to a telemarketing call at 5AM and saw somebody'd run over his mailbox in the middle of the night. Seriously, unless this is a technical class on how to write perfect proofs, anything less than a 6.5 is lame.

I had to drop a math class in college because I kept proving everything "the wrong way" and getting no credit for logically correct proofs, as if I were psychically supposed to know to write 2-page idiot proofs instead of efficient ones. Some professors are just horrible (and thankfully that one got fired after that semester).

[sirio11]

[ QUOTE ]
I had to drop a math class in college because I kept proving everything "the wrong way" and getting no credit for logically correct proofs, as if I were psychically supposed to know to write 2-page idiot proofs instead of efficient ones. Some professors are just horrible (and thankfully that one got fired after that semester).

[/ QUOTE ]

Same thing happened to me, all my problems were right and I keep getting 72 and 67 (still the highest) or so on. I drop the class after having a heavy discussion about how he needed some help about how to teach math, some of them just feel there is their only chance to feel powerful in life.

[tshort]

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

[/ QUOTE ]

If he had made his expectations on these proofs clear, he should give you maybe 6/7.

His first and third points seem valid and they were expected by my modern algebra professor on our induction proofs. She probably wouldn't have deducted points on your proof or a very small amount at most.

His second complaint of you using "weak induction" vs. "strong induction" is dumb as strong induction doesn't appear necessary for the proof.

[mathemagician54]

professors do this kind of thing when you're just learning induction to make sure you have the general structure understood. the proof is obviously right, and i don't like the policy but i can understand it. also you shouldn't be mad that there's induction in an algorithms class, you'll see it in any theoretical cs class.

that said, i do find it annoying... when induction was being taught in my intro CS classes they wanted the same kind of structure your professor wants. I missed the classes where they talked about the structure they wanted, so my proofs were like yours: correct but didn't follow the structure, and i got points off as well. not a big deal, just annoying.