Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Solve recursive equation:

$$ f_n = \frac{2n-1}{n}f_{n-1}-\frac{n-1}{n}f_{n-2} + 1$$ $f_0 = 0, f_1 = 1$

What I have done so far:

$$ f_n = \frac{2n-1}{n}f_{n-1}-\frac{n-1}{n}f_{n-2} + 1- [n=0]$$

I multiplied it by $n$ and I have obtained:

$$ nf_n = (2n-1)f_{n-1}-(n-1)f_{n-2} + n- n[n=0]$$ $$ \sum nf_n x^n = \sum(2n-1)f_{n-1}x^n-\sum (n-1)f_{n-2}x^n + \sum n x^n $$

$$ \sum nf_n x^n = \sum(2n-1)f_{n-1}x^n-\sum (n-1)f_{n-2}x^n + \frac{1}{(1-z)^2} - \frac{1}{1-z} $$

But I do not know what to do with parts with $n$. I suppose that there can be useful derivation or integration, but I am not sure. Any HINTS?

share|improve this question

3 Answers 3

up vote 3 down vote accepted

If $g(x)$ is your generating function, then $g'(x)=\sum nf_nx^{n-1}$, so $xg'(x)=\sum nf_nx^n$. Then

$$\sum(2n-1)f_{n-1}x^n=x\sum(2n+1)f_nx^n=2x^2g'(x)+xg(x)\;,$$

and you can handle the remaining summation similarly. I’ve not checked to see whether the resulting differential equation is nice or nasty. Note that your variable name changed from $x$ to $z$ in the last two terms.

share|improve this answer
    
I am not sure, but it should not be$\sum(2n-1)f_{n-1}x^n=x\sum(2n+1)f_{n-1}x^{n-1}$? Or maybe it does not matter? –  JosephConrad Apr 4 '13 at 19:03
    
@JosephConrad: I shifted the index one place. Think of it as substituting $m=n-1$: then $\sum(2n-1)f_{n-1}x^n=\sum(2m+1)f_mx^{m+1}$. Now pull out an $x$, and rename $m$ back to $n$. –  Brian M. Scott Apr 4 '13 at 19:05
    
Ok, I agree. Thanks a lot for help! I will try to finish this task with such substitution. –  JosephConrad Apr 4 '13 at 19:08
    
@JosephConrad: You’re welcome! –  Brian M. Scott Apr 4 '13 at 19:09

Let's take a shot at this: $$ f_n - f_{n - 1} = \frac{n - 1}{n} (f_{n - 1} - f_{n - 2}) + 1 $$ This immediately suggests the substitution $g_n = f_n - f_{n - 1}$, so $g_1 = f_1 - f_0 = 1$: $$ g_n - \frac{n - 1}{n} g_{n - 1} = 1 $$ First order linear non-homogeneous recurrence, the summing factor $n$ is simple to see here: $$ n g_n - (n - 1) g_{n - 1} = n $$ Summing: $$ \begin{align*} \sum_{2 \le k \le n} (k g_k - (k - 1) g_{k - 1}) &= \sum_{2 \le k \le n} k \\ n g_n - 1 \cdot g_1 &= \frac{n (n + 1)}{2} - 1 \\ g_n &= \frac{n + 1}{2} \\ f_n - f_{n - 1} &= \frac{n + 1}{2} \\ \sum_{1 \le k \le n} (f_n - f_{n - 1}) &= \sum_{1 \le k \le n} \frac{k + 1}{2} \\ f_n - f_0 &= \frac{1}{2} \left( \frac{n (n + 1)}{2} + n \right) \\ f_n &= \frac{n (n + 3)}{4} \end{align*} $$ Maxima tells me this checks out. Pretty!

share|improve this answer
    
Pretty impressive solution. Could you explain me 2 things: 1) what non-homogeneous recurrence stands for? 2) Why are we summing that equation ($ n g_n - (n - 1) g_{n - 1} = n $)? –  JosephConrad Apr 4 '13 at 19:57
    
@JosephConrad, (1) that is just the name for such an equation; (2) sum up to get the $n g_n$ (most of the rest of the sum telescopes away, the summing factor is designed to make this happen), same to get the $f_n$ in the end. Look closely, there shouldn't be any real mystery in this. –  vonbrand Apr 4 '13 at 20:02
    
Yes, now I understand what is going on :) Thanks for explanation! –  JosephConrad Apr 4 '13 at 20:14

Did you try difference equations? The original expression can be rewritten as (denote $\Delta f_k=f_{k}-f_{k-1}$) $$ \Delta f_{k}=\frac{k-1}{k}\Delta f_{k-1}+1 =\frac{k-1}{k} \cdot \frac{k-2}{k-1} \Delta f_{k-2} + \frac{k-1}{k}+1= \ldots =\frac{1}{k} \Delta f_1 + \frac{k-1}{k} \\ + \frac{k-2}{k-1}+\ldots + 1 = \frac{1}{k} \Delta f_1 + k - H_k $$ By summing both sides over $k$ and using boundary values you should get something like (I haven't checked the algebra!) $$ f_n= H_n + \frac{n(n+1)}{2}-(n+1)(H_n-1) $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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