solve non homogeneous recurrence relation with only '1' as root of its equation

Question

I'm stuck in this relation:

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

I've tried to search everywhere if I could find this kind of example where there is only root and that is '1' but all in vain. And all the previous experience of mine about recurrence relations has failed here because when we come to solve the non homogeneous part the two arbitrary variable cancel each other and we're left with nothing. Please somebody suggest how this can be done.

Answer 1

I am not completely sure if I understand correctly what you mean by "solving" the relation. However, I hope the following helps:

The relation can be written as $$f(n) - f(n-1) = 3n - 1$$ Hence,

$$f(n) = f(0) + \sum_{k=1}^n f(k) - f(k-1) = f(0) + \sum_{k=1}^n (3k - 1) = f(0) - n + 3\sum_{k=1}^n k$$

Using the summation formula for natural numbers $\sum_{k=1}^n k = n(n+1)/2$, we get $$f(n) = f(0) + \frac{3}{2} n(n+1) - n$$

Answer 2

Hint

Assume that $$f(n)=a+b n+c n^2$$ Replacing and expanding leads to $$f(n) -\big( f(n-1) + 3n - 1\big)=(2 c-3) n+(b-c+1)=0$$ Now, set all coefficients equal to zero.

I am sure that you can take from here.

Answer 3

HINT:

Let $f(n)=g(n)+An^2+Bn+C$

$3n-1=f(n)-f(n-1)=g(n)-g(n-1)+A(2n-1)+B$

$3n-1=g(n)-g(n-1)+2An+B-A$

Set $2A=3,-1=B-A$ to get $g(n)=g(n-1)$