| 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 | Specifically, I claimed its solution to be of the form<\/p>\n tn<\/sub> = a((1+5^0.5)\/2)^n + b((1-5^0.5)\/2)^n<\/p>\n We need to find a and b such that the tabulated values for tn<\/sub> come true. First of all, for n=0, we have<\/p>\n t0<\/sub> = a((1+5^0.5)\/2)^0 + b((1-5^0.5)\/2)^0<\/p>\n which simplifies to <\/p>\n 1=a+b<\/p>\n Next, for n=1, we have<\/p>\n t1<\/sub>=1=a((1+5^0.5)\/2)^1 + b((1-5^0.5)\/2)^1<\/p>\n which becomes, with b=1-a,<\/p>\n 1=a((1+5^0.5)\/2)^1+(1-a) + b((1-5^0.5)\/2)^1<\/p>\n Multiplying both sides by 2, we get<\/p>\n 2=a(1+5^0.5)+(1-a)(1-5^0.5)<\/p>\n which leads to<\/p>\n 2=a+a5^0.5+1-5^0.5-a+a5^0.5<\/p>\n and then<\/p>\n 2=2a5^0.5+1-5^0.5<\/p>\n Subtracting 1 then adding 5^0.5 to both sides gives<\/p>\n 5^0.5+1=2a5^0.5<\/p>\n Next, dividing both sides by 2(5^0.5), we get<\/p>\n (5^0.5 +1)\/(2(5^0.5))=a<\/p>\n Recalling that b=1-a, we have<\/p>\n b=(5^0.5 -1)\/(2(5^0.5))<\/p>\n Believe it or not, the solution to the tabulated recurrence relation is<\/p>\n tn<\/sub> = (5^0.5 +1)\/(2(5^0.5))((1+5^0.5)\/2)^n + (5^0.5 -1)\/(2(5^0.5))((1-5^0.5)\/2)^n Grimaldi, Ralph P. Discrete and Combinatorial Mathematics<\/u>. Don Mills: |