% V02 of generalized_Fibonacci, updated 20/09/28 by Wei-Cheng Wang. % to demonstrate stability and instability of recurrence formula % pay attention at line 49 for the textbook case. clear; format long; % n = 73 is near overflow, stay below it. n=50; a=zeros(1,n); ar=zeros(1,n); a_true=zeros(1,n); % Need to enforce c2 = 0 only for these cases % The case in the slides: % a(1) = 1; a(2) = 1/3 ; b = 13/3; c=-4/3; force_c2_zero = true; % % The case in textbook: % a(1) = 1/3; a(2) = 1/9; b = 10/3; c=-1; force_c2_zero = true; % same as above, in principle (a(2) = 1/9) % a0 = 1; a(1) = 1/3; b = 10/3; c=-1; a(2) = b*a(1)+c*a0; force_c2_zero = true; % more cases with c2=0 % a(1) = 1/5; a(2) = 1/10; b = 9/2; c = -2; force_c2_zero = true; % Other cases cases, c2 neq 0 % a(1) = 1; a(2) = 1/4; b = 10/3; c=-1; force_c2_zero = false; %only minor difference from above case % a(1) = 1/5; a(2) = 1/5 ; b = 9/2; c = -2; force_c2_zero = false; a(1) = 1; a(2) = 1.1; b = 1; c = 1; force_c2_zero = false; % Some cases that can computed without error for n = 70 (why?): % a(1) = 1; a(2) = 1/2 ; b = 9/2; c = -2; force_c2_zero = false; % a(1) = 1; a(2) = 1/2; b = 5/2; c = -1; force_c2_zero = false; for i = 3:n a(i) = b*a(i-1) + c*a(i-2); end recusively_computed_an = a(n) % true solution: a_true(i) = c1*lambda_1^i + c2*lambda_2^i; % c1, c2 can be obtained from a(1), a(2) % or from a(0) and a(1). % Here is the formula using a(0) and a(1). a0 = ( a(2)-b*a(1) )/c ; lambda_1 = (b - sqrt(b^2+4*c))/2; % lambda_1 = -2*c/(b + sqrt(b^2+4*c)) %alternative formula for b>0, |c|<