1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Ana S. H. Oct 14 '16 at 17:35
  • $\begingroup$ @Ana But do I then get a closed formula without numbers, like the one I've already wrote? $\endgroup$ – Matriz Oct 14 '16 at 18:22
  • $\begingroup$ Yes. Check the answer of dxiv below. You just need your initial condition. $\endgroup$ – Ana S. H. Oct 14 '16 at 20:09
  • 1
    $\begingroup$ @Ana Ok thank you very much for your help! $\endgroup$ – Matriz Oct 15 '16 at 9:56
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)$$ $\endgroup$ – Matriz Oct 14 '16 at 23:10
  • 1
    $\begingroup$ 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}$$ $\endgroup$ – dxiv Oct 14 '16 at 23:20
  • 1
    $\begingroup$ Thank you very very much for your help! $\endgroup$ – Matriz Oct 15 '16 at 10:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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