# How to solve this linear recurrence relation

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.

• Hint: add something to both sides and make a well-known, simpler sequence. – Neat Math Nov 4 '20 at 2:38
• 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 ^_^ – HallaSurvivor Nov 4 '20 at 3:06
• @NeatMath I'm not aware of well known simpler sequences. can you please give an example of how would you simplify it? – fxnoob Nov 4 '20 at 3:28
• $g(n)=3 *g(n-1)$ would be simpler. Try adding $2$ to both sides of your relation – J. W. Tanner Nov 4 '20 at 3:29
• 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. – fxnoob Nov 4 '20 at 3:57

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$$.