I will be doing Question 3 /Assignment 2 using Polya's method which we learned in CSC165
QUESTION: Let G(n) be the number of ways a grasshopper can perform the climb when there are n stairs. Prove that for n >= 1, G(n) <= F(n), the nth Fibonacci number.
Step One: Understand the ProblemThe main task in this question is to find a formula for G(n) and use it to prove that G(n) <= F(n) using complete induction. Since professor Danny does not require a closed formula for G(n), I will just try to find a recursive one.
Step Two: Devise a Plan
The first plan that came up to my mind is to try and find G(n) for some small values of n, and then by comparing these values with each other on one hand, and with n on the other hand, come up with a formula. After finding the formula, establish a predicate, a claim, then start the inductive proof.
Step Three: Carry out the Plan
Let's make a table for 1 <= n <= 8 and write down all the possible configurations of hops that the grasshopper can make to reach the nth step:
*****I do not know where did this space come from*****
n |
Possible Configurations |
G(n) |
1 |
1 |
1 |
2 |
11 |
1 |
3 |
111, 3 |
2 |
4 |
1111, 31, 13 |
3 |
5 |
11111, 311, 113, 131 |
4 |
6 |
111111, 33, 1113, 1131, 1311, 3111, |
6 |
7 |
1111111, 331, 313, 331, 11131, 11131, 11311, 13111, 31111, |
9 |
8 |
11111111, 3311, 3131, 3113, 1133, 1331, 111113, 111131, 111311, 113111, 131111, 311111, |
13 |
Looking at the previous table, we can tell that G(n) will depend on the addition and subtraction of other values of G(n) becaue G(n), like F(n), does not seem to increase fast. (so we do not have exponential powers for example). Other than this observation, there does not seem to be a clear pattern that can be used. For example, for 2 <= n <= 4, G(n) = G(n-1) + G(n-2). For 5 <= n <= 7, G(n) = G(n-1) + G(n-2) -1. This does not seem to work; I need another plan. I know that the formula is there but I cannot seem able to derive it. I will work on another plan tomorrow.
Step Two (b): Devise an alternative Plan
The previous plan did not seem to work out well so I had to come up with something else. This time, in stead of finding a formula that works for small values of n and then generalizing it, I will try to come up with something directly general.
Step Three (b): Carry out the Plan1) Suppose that the grasshopper wants to get to step m. Then, the grasshopper must be at step m -1 since it can an hop 1 step. But since it can hop 3 hops as well, then it can be at step m - 3 as well. Because this is a recursive formula, we know that there are some number of configurations that make the grasshopper get to step m-1 . There is also another set of configurations that make it get to step m-3. Since G(n) is about the order of steps used to climb the stairs, then we can get to m by the number of configurations for m-1 (with 1 added to the end of each configuration) plus the number of configurations for m -3 (with 3 added to the end of each configuration).
Then, G(m) = G(m-1) + G(m-3); and this formula actually works for the values of n in the table.
We have to make a special consideration for the values of n <= 3 since (n-1) and/or (n-3) might no be defined. Then: G(n) = {1, if n=1 or n = 2
2, if n = 3
G(n -1 ) + G(n -3) if n > 3
2) Before we start the proof, we need to prove that the Fibonacci Sequence is non-decreasing.
Predicate P(n): ∀ n,g ∈ ℕ, g < n \implies F(g) <= F(n)
Claim: ∀ n ∈ ℕ, P(n)
Use complete induction; then we need to prove the following:
∀ n ∈ ℕ, [P(0)\and P(1) ..... \and P(n-1)] \implies P(n)
Base Cases:
When n = 0, then there is no smaller natural number. Hence, we cannot find a g such that g <> F(n). Hence, P(0) is true.
When n = 1, then the only smaller natural number is 0 and P(0) = 0 < 1 = P(1).
Hence, P(1) is true.
Induction Step:
Assume n ∈ ℕ
Assume P(0)\and P(1) ..... \and P(n-1) are true # Induction Hypothesis
If n <= 1, then P(n) holds as shown in the base cases
Else if n > 1
Then F(n - 1) = F(n-2) + F(n-3) <= F(n-1) + F(n-2) = F(n) # By IH
Then F(n - 1) <= F(n) \and (n-1) < n
Then P(n) holds
Then [P(0)\and P(1) ..... \and P(n-1)] \implies P(n)
Then ∀ n ∈ ℕ, [P(0)\and P(1) ..... \and P(n-1)] \implies P(n)
Conclude: ∀ n ∈ ℕ, F(n) is non-decreasing
3) Now that we have a formula for G(n) and we know that the Fibonacci Sequence is non-decreasing, we can establish a predicate and claim.
Predicate P(n): if n ∈ ℕ - {0}, G(n) <= F(n) Claim: ∀ n ∈ ℕ - {0}, P(n) We will use complete induction. Then we need to prove the following: ∀ n ∈ ℕ - {0}, P(1) \and P(2) ............... \and P(n -1) \implies P(n)
Base cases: When n = 0, then P(0) holds automatically. When n = 1, then G(1) = 1 <= F(1) = 1 When n = 2, then G(2) = G(1) = 1 <= F(1) <= F(2) When n = 3, then G(3) = 2 <= G(2) = 1 <= F(1) <= F(2) Then P(n) holds in all base cases.
Induction Step:Assume n \in N and n > 0
Assume P(1)\and P(2) ..... \and P(n-1) are true # Induction Hypothesis
If n <= 3, then P(n) holds as shown in the base cases. Else if n > 3:
Then G(n) = G(n-1) + G(n-3) <= F(n-1) + F(n-3) # By IH and definition of G(n), F(n) Then F(n-1) + F(n-3) <= F(n-1)+ F(n-2) = F(n) # Since the Fibonacci Sequence is non-decreasing Then G(n) <= F(n) Then P(n) holds
Then ∀ n ∈ ℕ - {0}, [P(1)\and P(2) ..... \and P(n-1)] \implies P(n)
Conclude: ∀ n ∈ ℕ - {0}, G(n) <= F(n) Step Four: Look Back
So we have found a formula for G(n),and we explained how we derived it. We proved that the Fibonacci Sequence is non-decreasing and used this property in out inductive proof. Then we can conclude that ∀ n ∈ ℕ - {0}, G(n) <= F(n).
