# Difficult recurrence relation

I'm trying to find through generating function a closed form of the following recursion:

$$g_n=f_n+t_ng_{n+1}\qquad n\in \mathbb{N}_0$$

where $$f_n, t_n$$ are some elements of an unknown sequence.

So it's clear for me, that the closed form of the recurrence relation should end up like this

$$g(n)=f_n+\sum\limits_{i=n}^\infty f_i \prod\limits_{j=0}^{i-1} t_j$$

I tried different approaches, but the example seems very hard and confusing since the sequence is decreasing and I have two unkown factors $$t_n,f_n$$. All I find on the internet are simple sequences.

So first let's rewrite it:

$$g_n-f_n-t_ng_{n+1}=0$$

And write some elements of sequence: $$g_0 = f_0+t_0g_{1}=f_0+t_0(f_1+t_1g_2)=f_0+t_0f_1+t_0t_1f_2+t_0t_1t_2g_{3}....$$ $$g_1 = f_1+t_1g_2=f_1+t_1(f_2+t_2g_3)=f_1+t_1f_2+t_1t_2g_3=f_1+t_1f_2+t_1t_2(f_3+t_3g_4)....$$ $$g_2 = f_2+t_2g_3=f_2+t_2(f_3+t_3g_4)=f_2+t_2f_3+t_2t_3g_4=f_2+t_2f_3+t_2t_3(f_4+t_4g_5)....$$

So the first approach I did was to define $$A=ax+bx^2+cx^3...$$ $$xA=ax^2+bx^3+cx^4...$$ $$x^2A=ax^3+bx^4+cx^5...$$

But this doesn't work, since I have this factor $$t_n$$. Or Atleast I don't find a way.

So my second approach was to remove those factors:

$$xA=f_0+t_0f_1x+t_0t_1f_2x^2+t_0t_1t_2g_{3}x^3....$$ $$\frac{x^2}{t_0}(A-f_0)=f_1x^2+t_1f_2x^3+t_1t_2g_{3}x^4....$$ $$\frac{x^3}{t_0t_1}(A-f_0-f_1)=f_2x^4+t_2g_{3}x^5....$$

But now I can not subtract the lines and remove elements.

So my thrid approach was to remove the $$x$$ also

$$A=f_0+t_0f_1x+t_0t_1f_2x^2+t_0t_1t_2g_{3}x^3....$$ $$\frac{1}{t_0x}(A-f_0)=f_1+t_1f_2x+t_1t_2g_{3}x^2....$$ $$\frac{1}{t_1t_0x^2}(A-f_0-f_1)=f_2+t_2f_3x+t_2t_3f_4x^2+t_2t_3t_4g_5x^4....$$

But I don't see how this helps me and what I should do now.

The fourth approach I did was to work with

$$\sum\limits_{n=0}^\infty g_n = \sum\limits_{n=0}^\infty f_nx^n -\sum\limits_{n=0}^\infty t_ng_{n+1}x^n$$ $$\sum\limits_{n=0}^\infty (g_n-f_n)x^n -\sum\limits_{n=0}^\infty t_ng_{n+1}x^n=0$$

If I now chose rewrite $$g_{n+1}$$ I get $$g_n=f_n+t_ng_{n+1}\implies g_{n+1}=\frac{g_n-f_n}{t_n}$$ But If I put this in the equation I get the exact same thing on the RHS as I have on the LHS. $$\sum\limits_{n=0}^\infty (g_n-f_n)x^n -\sum\limits_{n=0}^\infty t_n\frac{g_n-f_n}{t_n}x^n=0$$ $$\sum\limits_{n=0}^\infty (g_n-f_n)x^n -\sum\limits_{n=0}^\infty (g_n-f_n)x^n=0$$ Please help me. I'm in despair since days and I don't know what to do. Every example on the internet look much easier than this.

• I think you need an initial condition. Say $g_0=1$. Then you can apply recursively your relation until arriving to $g_n$ in terms of $g_0$. Oct 14, 2016 at 17:35
• @Ana But do I then get a closed formula without numbers, like the one I've already wrote?
– user185346
Oct 14, 2016 at 18:22
• Yes. Check the answer of dxiv below. You just need your initial condition. Oct 14, 2016 at 20:09
• @Ana Ok thank you very much for your help!
– user185346
Oct 15, 2016 at 9:56

## 1 Answer

\begin{align} g_{n+1} & =\frac{1}{t_n}g_n-\frac{f_n}{t_n} \\ & = \frac{1}{t_n}(\frac{1}{t_{n-1}}g_{n-1}-\frac{f_{n-1}}{t_{n-1}})-\frac{f_n}{t_n} \\ & = \frac{1}{t_n t_{n-1}} g_{n-1} - \frac{f_{n-1}}{t_n t_{n-1}} - \frac{f_n}{t_n} \\ & = \cdots \\ & = \frac{1}{\prod_{k=0}^n t_k} g_0 - \sum_{k=0}^n \frac{f_k}{\prod_{j=k}^n t_j} \end{align}

• Thank you very much! I would have never figured that out. I'm a little bit confused, if I chose some $g_0$ and plug your result into the recurrence equation, do I already have the closed form? $$g_n=f_n+t_n\left(\frac{1}{\prod_{k=0}^n t_k} g_0 - \sum_{k=0}^n \frac{f_k}{\prod_{j=k}^n t_j}\right)$$ $$g_n=f_n+\left(\frac{1}{\prod_{k=0}^{n-1} t_k} g_0 - \sum_{k=0}^n \frac{f_k}{\prod_{j=k}^{n-1} t_j}\right)$$ $$g_n=f_n+\left(\frac{1}{\prod_{k=0}^{n-1} t_k} g_0 - \sum_{k=0}^n \frac{f_k}{\prod_{j=k}^{n-1} t_j}\right)$$
– user185346
Oct 14, 2016 at 23:10
• Sorry, not sure I follow the comment. The closed form is the one given in my answer. If you want the expression for $g_n$ (instead of $g_{n+1}$) then just replace $n+1 \to n$ (for $n \ge 1$):$$g_n = \frac{1}{\prod_{k=0}^{n-1} t_k} g_0 - \sum_{k=0}^{n-1} \frac{f_k}{\prod_{j=k}^{n-1} t_j}$$
– dxiv
Oct 14, 2016 at 23:20
• Thank you very very much for your help!
– user185346
Oct 15, 2016 at 10:32