@yuyutsu
I told that so that we can get close to the solution.
Our recurrence is $u(k) = 5u(k-1) + u(k-1 + \log_3 2) + 1$
Suppose, $u(k) = 9^k,$ it means it should satisfy the given recurrence. So, if we put it in the right side of the recurrence then we get,
$5*9^{k-1} + 9^{k-1 + \log_3 2} + 1 = 5*9^{k-1} + 9^{k-1}*9^{\log_3 2} +1$
$= 5*9^{k-1} + 9^{k-1}*3^{\log_3 2^2} + 1 = 5*9^{k-1} + 4*9^{k-1} + 1 = 9*9^{k-1} + 1$
$=9^k + 1$
It means $u(k) = 9^k$ is not the absolutely correct solution. If $u(k) = 5u(k-1) + u(k-1 + \log_3 2)$ then it would be the correct solution.
But it is very close to the correct solution because $|u(k) – 9^k| = 1.$ Here you can say relative error is $1$ which is very less and constant. If you calculate $u(1),u(2),u(3),...$ then the difference between the actual value of $u(1),u(2),u(3),...$ and those values which solution $9^k$ provides, will be $1$ and that’s why we are saying $|u(k) – 9^k| = 1.$ and if $k$ is a very large value then also you will get difference as $1.$
So, you can say, $u(k) \approx 9^k$
Now, suppose, $u(k) = 8^k,$ if we put it in the right side of the recurrence, we get, $1.09*8^k + 1$
and now the relative error is $1.09*8^k + 1 – 8^k=0.09*8^k +1 $ which is not a constant and gets bigger and bigger when $k$ is approaching to infinity.
Now, suppose, $u(k) = 7^k,$ if we put it in the right side of the recurrence, we get, $1.20*7^k + 1$
and now the relative error is $1.20*7^k + 1 – 7^k=0.20*7^k +1 $ which is also not a constant and gets bigger and bigger when $k$ is approaching to infinity.
Now, suppose, $u(k) = 10^k,$ if we put it in the right side of the recurrence, we get, $0.92*10^k + 1$
and now the relative error is $|0.92*10^k + 1 – 10^k|=|-0.07*10^k +1| $ which is also not a constant and gets bigger and bigger when $k$ is approaching to infinity.
So, we get the less error in only $u(k) \approx 9^k$ and the less error we get, the more accurate we are :P
