Chapter 3: assignement 2

In the assignment 2, we need to get close form of H(n) = H(n-1) + H(n-2) if n >2. Then based on the skill we are taught form lecture, we get H(n) = F(n + 1) by unwind. We already know the close form of Fibonacci.  So, we get final close form that combines both of H(n) = F(n+1) and Fibonacci close form.

In the book of “mcs” that is the textbook of CSC240. The author uses the method that is to prove Fibonacci to prove H(n). So, author gets a homogeneous linear form first: f(n) = a1f(n-1) + a2f(n-2) + …adf(n-d). Then get x = (1+sqr(5))/2. Quoting the theorem 21.31: if f(n) and g(n) are both solutions to a homogeneous linear recurrence, then h(n) = sf(n) + tg(n) is also a solution for all s and t of Real number, author get the same answer.

It looks that the former way is easier. But three authors of “mcs” are professors of MIT and researcher of Google. Why do they not to use that method to prove this? I has just a little bit of confusion.