Problem Solving with Polya
Well, since A2 was due about a week ago and last year I lost a lot of marks for not doing this, it's time to document an attempt at problem solving using Polya's method.
Since I am a horrible person, I've never actually used Polya's method for anything, but maybe if I did I'd be doing better in this course.
The problem in question is number 3 from Assignment 2 or...
Consider a grasshopper that can hop up the stairs either 1 or 3 steps at a time. Let G(n) be the number of ways it can perform the climb when there are n stairs. Prove that for n >= 1, G(n) <= F(n), the nth Fibonacci number.
1. UNDERSTANDING THE PROBLEM
In order to understand the problem, you need to know what the Fibonacci numbers are and how to find them: F(n) and a formula for how many ways a grasshopper can climb n steps in either 1 or 3 step increments: G(n).
F(n) is widely known to be:
F(n) = 1, if n = 1, 2 (or if n = 0, 1 but both work for this problem)
= F(n - 1) + F(n - 2), if n > 2
However G(n) is unique to this problem and will need to be solved somehow before it's possible to prove G(n) <= F(n) for all n > 0
2. DEVISING A PLAN
Well, it's obviously going to be necessary to solve for G(n) at some point.
When I originally did this problem, I remembered that whenever we did questions in the past with Fibonacci we used induction and said that F(n) = F(n - 1) + F(n - 2) and then used our induction hypothesis so if we assumed F(n) >= G(n) then F(n - 1) + F(n - 2) >= G(n - 1) + G(n - 2).
Unfortunately at this point it was 4am and I didn't stop and think that whenever we did problems like this whatever we were comparing F(n) to was also a recursive formula.
Had I done this I would have not wasted a large amount of my time.
I also thought that after I had a formula for G(n), proving it was less than or equal to F(n) would be so easy that finding a formula for G(n) must be the hard part.
3. CARRYING OUT THE PLAN
I then, eager to put my stats knowledge and ternary trees mode of thinking to good use, came up with an overly complicated sum of multiple summations formula for G(n) with multiple factorials thrown in haphazardly.
I then tried to prove this was less than F(n) for a few hours without thinking about restating things or finding an alternate formula for G(n) or even thinking more about related questions as recommended by Polya. I tried checking each step and each time caught several horrible fallacies but my proof was still not within grasp.
Around 6am, I gave up and crawled to bed and then woke up about 3 hours later and attempted other questions while trying to forget about how much that grasshopper was annoying me.
Around noon, I did an important thing Polya never mentioned in his method: I harassed Daniyar in the dining hall and asked how he did it. He seemed surprised and stated that the question was easy just comparing two recursive formulas. At this point, I loudly swore and realised my mistake and brooded over my failure while eating fruit loops and cereal which at least allowed me to also brood over what a horrible person I was for eating refined sugar instead of simply contemplating switching into something useless and boring like a double major in Anthropology and Women's Studies.
I then ran up to my room and attempted to look for a recursive formula for G(n) and REVISE my plan.
After I saw the simple formula G(n) = G(n - 1) + G(n - 3), I resisted the urge to bang my head on my desk and typed up a blurb to convince myself and whoever marks my assignment on why this is the correct formula.
Essentially, the grasshopper can only reach the nth step by jumping one step from n - 1 steps or 3 steps from n - 3 steps.
I then carried out the second part of my original plan and realised how much easier it was.
Assume G(n) <= F(n) for all n <= k - 1
F(k) = F(k - 1) + F(k - 2) # def of F(n)
>= G(k - 1) + G(k - 2) # inductive hypothesis
= G(k - 1) + G(k - 3) + G(k - 5) # def of G(n)
= G(k) + G(k - 5) # def of G(n)
>= G(n) # since G(n) is nondecreasing
Ofcourse you'd need a nice base case and prove G(n) is nondecreasing but both of those are easy.
4. LOOKING BACK
Well, since it's a proof it's not really necessary to prove it works, but after reviewing my answer I discovered all that was really necessary to solve the problem easily was finding G(n) and the nice simple recursive version of G(n) resulted in the same answer as my disgusting summation version but not only was considerably easier to read but made proving the statement G(n) <= F(n) quite simple.
Since I am a horrible person, I've never actually used Polya's method for anything, but maybe if I did I'd be doing better in this course.
The problem in question is number 3 from Assignment 2 or...
Consider a grasshopper that can hop up the stairs either 1 or 3 steps at a time. Let G(n) be the number of ways it can perform the climb when there are n stairs. Prove that for n >= 1, G(n) <= F(n), the nth Fibonacci number.
1. UNDERSTANDING THE PROBLEM
In order to understand the problem, you need to know what the Fibonacci numbers are and how to find them: F(n) and a formula for how many ways a grasshopper can climb n steps in either 1 or 3 step increments: G(n).
F(n) is widely known to be:
F(n) = 1, if n = 1, 2 (or if n = 0, 1 but both work for this problem)
= F(n - 1) + F(n - 2), if n > 2
However G(n) is unique to this problem and will need to be solved somehow before it's possible to prove G(n) <= F(n) for all n > 0
2. DEVISING A PLAN
Well, it's obviously going to be necessary to solve for G(n) at some point.
When I originally did this problem, I remembered that whenever we did questions in the past with Fibonacci we used induction and said that F(n) = F(n - 1) + F(n - 2) and then used our induction hypothesis so if we assumed F(n) >= G(n) then F(n - 1) + F(n - 2) >= G(n - 1) + G(n - 2).
Unfortunately at this point it was 4am and I didn't stop and think that whenever we did problems like this whatever we were comparing F(n) to was also a recursive formula.
Had I done this I would have not wasted a large amount of my time.
I also thought that after I had a formula for G(n), proving it was less than or equal to F(n) would be so easy that finding a formula for G(n) must be the hard part.
3. CARRYING OUT THE PLAN
I then, eager to put my stats knowledge and ternary trees mode of thinking to good use, came up with an overly complicated sum of multiple summations formula for G(n) with multiple factorials thrown in haphazardly.
I then tried to prove this was less than F(n) for a few hours without thinking about restating things or finding an alternate formula for G(n) or even thinking more about related questions as recommended by Polya. I tried checking each step and each time caught several horrible fallacies but my proof was still not within grasp.
Around 6am, I gave up and crawled to bed and then woke up about 3 hours later and attempted other questions while trying to forget about how much that grasshopper was annoying me.
Around noon, I did an important thing Polya never mentioned in his method: I harassed Daniyar in the dining hall and asked how he did it. He seemed surprised and stated that the question was easy just comparing two recursive formulas. At this point, I loudly swore and realised my mistake and brooded over my failure while eating fruit loops and cereal which at least allowed me to also brood over what a horrible person I was for eating refined sugar instead of simply contemplating switching into something useless and boring like a double major in Anthropology and Women's Studies.
I then ran up to my room and attempted to look for a recursive formula for G(n) and REVISE my plan.
After I saw the simple formula G(n) = G(n - 1) + G(n - 3), I resisted the urge to bang my head on my desk and typed up a blurb to convince myself and whoever marks my assignment on why this is the correct formula.
Essentially, the grasshopper can only reach the nth step by jumping one step from n - 1 steps or 3 steps from n - 3 steps.
I then carried out the second part of my original plan and realised how much easier it was.
Assume G(n) <= F(n) for all n <= k - 1
F(k) = F(k - 1) + F(k - 2) # def of F(n)
>= G(k - 1) + G(k - 2) # inductive hypothesis
= G(k - 1) + G(k - 3) + G(k - 5) # def of G(n)
= G(k) + G(k - 5) # def of G(n)
>= G(n) # since G(n) is nondecreasing
Ofcourse you'd need a nice base case and prove G(n) is nondecreasing but both of those are easy.
4. LOOKING BACK
Well, since it's a proof it's not really necessary to prove it works, but after reviewing my answer I discovered all that was really necessary to solve the problem easily was finding G(n) and the nice simple recursive version of G(n) resulted in the same answer as my disgusting summation version but not only was considerably easier to read but made proving the statement G(n) <= F(n) quite simple.
posted by Katie at
9:57 PM
0 Comments:
Post a Comment
Subscribe to Post Comments [Atom]
<< Home