0
$\begingroup$

how to solve following recurrence relation :

$f(n) = 3 * f(n - 1) + 4$

i've got that recurrence relation from following sequence, where f(n) is nth value of the following sequence.

$7, 25, 79, 241, 727, 2185$, and so on.

So $f(0) = 7$, $f(1) = 25$. etc.

$\endgroup$
5
  • 1
    $\begingroup$ Hint: add something to both sides and make a well-known, simpler sequence. $\endgroup$ – Neat Math Nov 4 '20 at 2:38
  • $\begingroup$ Welcome to MSE! What have you tried? Where do you feel like you're struggling? We can help you better once we know where the issue is ^_^ $\endgroup$ – HallaSurvivor Nov 4 '20 at 3:06
  • $\begingroup$ @NeatMath I'm not aware of well known simpler sequences. can you please give an example of how would you simplify it? $\endgroup$ – fxnoob Nov 4 '20 at 3:28
  • $\begingroup$ $g(n)=3 *g(n-1)$ would be simpler. Try adding $2$ to both sides of your relation $\endgroup$ – J. W. Tanner Nov 4 '20 at 3:29
  • $\begingroup$ NeatMath ,j W Tanner thank you. i've realized it now. . @HallaSurvivor thank you :) I'm trying to develop iterative algorithm for modified version of Ackermann Function which is defined in recursive terms. I want to evaluate it for large value of n. Doing it with recursive approach is easy but that is busting out programs 'call stack' even for n = 4 and now i know it why. $\endgroup$ – fxnoob Nov 4 '20 at 3:57
1
$\begingroup$

The hint from Neat Math suggests $f(n)=3f(n-1)+4\iff f(n)+2=3(f(n-1)+2)$

or $g(n)=3g(n-1)$ where $g(n)=f(n)+2$, so $g(n)=3^{n}g(0)$, with $g(0)=9$,

so $g(n)=3^{n+2}$, so $f(n)=3^{n+2}-2$.

A more pedantic solution would be the following:

$f(n)-3f(n-1)=f(n-1)-3f(n-2)$, so $f(n)=4f(n-1)-3f(n-2)$.

The roots of the characteristic equation $r^2=4r-3$ are $r=1,3$,

so the solution is $f(n)=A\cdot3^n+B\cdot1^n$.

Solve for $A$ and $B$ given $f(0)=7$ and $f(1)=25$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.