Problem-Solving Episode

Here's my problem-solving episode using the approach suggested by Polya (http://www.math.utah.edu/~alfeld/math/polya.html). I decided to do this on Q3 of Assignment #2.

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. For example, G(4) = 3, since the grasshopper can jump four stairs as either 1 + 1 + 1 + 1, or 1 + 3, or 3 + 1. Prove that for n >= 1, G(n) <= F(n), the nth Fibonacci number.

1. UNDERSTANDING THE PROBLEM

Let's look at some base cases:

G(1) = 1
G(2) = 1
G(3) = 2
G(4) = 3
G(5) = 4
G(6) = 6
G(7) = 9
G(8) = 13

2. DEVISING A PLAN

A grasshopper can hopup eaither 1 or 3 steps at a time. Therefore, he can reach nth stair using 1 1-hop from n-1th stair or using a 3-hop from n-3th stair. Therefore, the number of ways a grasshopper can climb up n stairs can be further subdivided into:

The number of ways he can climb up n-3 stairs + The number of ways he can climb up n-1 stairs

Therefore, for n >= 4:
G(n) = G(n-1) + G(n-3)
F(n) = F(n-1) + F(n-2),

Where F(n) is the nth Fibonacci number.

3. CARRYING OUT THE PLAN

Assume : n is an arbitrary natural number.
P(1) and ... and P(n-1) are true.

Base Case:
If n=1 then G(1) = 1 <= F(1) = 1
n=2 then G(2) = 1 <= F(2) = 1
n=3 then G(3) = 2 <= F(3) = 2

Induction Step:
Consider F(n) - G(n) = [F(n-1) + F(n-2)] - [G(n-1) + G(n-3)]
= [F(n-1) - G(n-1)] + [F(n-2) - G(n-3)]

We know F(n-1) - G(n-1) >= 0, by I.H.
F(n-2) - G(n-3) >= F(n-2) - G(n-2) , by def of G(n)
>= 0 , by I.H

Therefore, [F(n-1) - G(n-1)] + [F(n-2) - G(n-3)] >= 0
F(n) - G(n) >= 0
F(n) >= G(n)

4. LOOKING BACK

Therefore, we have proven forall n>=1 G(n) <= F(n).