Non homogeneus recurrence relation

Question

I am trying to solve the next relation to get the general form for calculate the space compexity of an algoritm.

$$ f(x)=f(x-1)+4g(x)+4g(\frac{x}{2})+4 $$ where $$ f(1)=g(1)=23 $$ $$ g(x)=18x+5 $$

The solution i got for the homenegous solution is $$ f^{H}(x)=\lambda_{1}3^{n} $$

For the particular solution, i did $$ f^{P}(x)=c $$ $$ c=3c+4g(1)+4g(0,5)+4 $$ $$ 0=2c+4g(1)+4g(0,5)+4 $$ $$ c=-76 $$

but i think is wrong evaluate g(1) but i don't know how to follow

Thank you in advance

Answer 1

Maybe there is a problem with the modelling prior to your equation, but with $g(x)$ given explicitly, the recurrence boils down to

$$f(x) = f(x-1) + 108x + 44$$

Since you are only interested in integer values of x, then the solution to this recurrence is

$$f(x) = 54x^2 + 98x + c$$

With $f(1)=23$ we finally get

$$f(x)=54x^2 + 98x - 129$$

Answer 2

I don't know what you are talking about when you say "homogenous equation" in this specific case, but you should be able to prove that $\displaystyle f(x) = f(1) + \sum_{i=2}^x 4g(i) + \sum_{i=2}^x4g(\frac i2) + \sum_{i=2}^x4$, by immediate recursion.

From this, you conclude that $f(x) = 54x^2 + 98x - 129$, for any $x \geq 1$.