0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ "all in vain" Very surprising: first there are tons of examples of this on the site, second, direct analysis shows that if $f(n)=f(n-1)+g(n)$ for every $n$ then $f(n)=f(0)+\sum\limits_{k=1}^ng(k)$ for every $n$ (here $g(n)=3n-1$). $\endgroup$
    – Did
    Aug 24, 2015 at 11:28
  • $\begingroup$ Well, if so, I was confused a lot to understand any of them. But now I get it along with the solution $\endgroup$
    – lavee_singh
    Aug 25, 2015 at 6:45
  • $\begingroup$ I can't improve the question anymore, the given question was the exact query I had. $\endgroup$
    – lavee_singh
    Aug 25, 2015 at 9:33

3 Answers 3

Reset to default
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This is perfectly correct answer, this is the one I was looking for. I was unable to get something, now I get it. $\endgroup$
    – lavee_singh
    Aug 25, 2015 at 6:42
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .