Back in my June 21 post,<\/a> the following recurrence relation emerged:<\/p>\n
| n<\/td>\n | tn<\/sub><\/td>\n<\/tr>\n| 0<\/td>\n | 1<\/td>\n<\/tr>\n | 1<\/td>\n | 1<\/td>\n<\/tr>\n | 2<\/td>\n | 2<\/td>\n<\/tr>\n | 3<\/td>\n | 3<\/td>\n<\/tr>\n | 4<\/td>\n | 5<\/td>\n<\/tr>\n<\/table>\n | The tabulated relationship above can be written as tn+2<\/sub>=tn+1<\/sub>+tn<\/sub>, and then as tn+2<\/sub> – tn+1<\/sub> – tn<\/sub> = 0<\/p>\n The equation above is a second degree homogeneous recurrence equation. Its general solution will be of the form<\/p>\n tn<\/sub>=as1<\/sub>^n + bs2<\/sub>^n,<\/p>\n where s1<\/sub>, s2<\/sub> are the solutions to the related quadratic equation<\/p>\n x^2-x-1=0<\/p>\n Using the quadratic formula (see my post here<\/a>), we get<\/p>\n x=(1+5^0.5)\/2 or x=(1-5^0.5)\/2<\/p>\n So the general solution to the recursive equation tn+2<\/sub> – tn+1<\/sub> – tn<\/sub> = 0 will be<\/p>\n tn<\/sub> = a((1+5^0.5)\/2)^n + b((1-5^0.5)\/2)^n<\/p>\n where a,b are constants to determine. Next post, I’ll show how to determine a and b in order to arrive at the definitive solution.<\/p>\n Source:<\/p>\n Grimaldi, Ralph P. Discrete and Combinatorial Mathematics<\/u>. Don Mills: |