In modelling a certain problem I find the following sum that I am trying to find a formula for $f_1+f_2+f_3...+f_n$ where \begin{align} &f_1=t_1+(a+y(t_1-t_0))k\\ &f_2=t_1+\Bigg(a+2y(t_1-t_0)+\bigg(\Big(a+y(t_1-t_0)\Big)k-ak\bigg)y\Bigg)k\\ &f_3=t_1+\Bigg(a+3y(t_1-t_0)+\bigg(\Big(a+y(t_1-t_0)\Big)k-ak\bigg)y \\ &+ \bigg(\bigg(a+2y(t_1-t_0)+\Big(\big(a+y(t_1-t_0)\big)k-ak\Big)y\bigg)k-ak\bigg)y\Bigg)k\\ &.\\ &.\\ &.\\ \end{align} Notice that the equation of $f_3$ takes up two lines. I found that $f_n$ is given by the recursive formula \begin{align} f_n=t_1+k\bigg( a+ny(t_1-t_0)+y\sum_{i=1}^{n-1} (f_i-t_1-ak) \bigg),\;\;\;\;\; f_1= t_1+k(a+y(t_1-t_0)) \end{align} I know it is very messy and probably very hard to find a formula for the sum or even a non-recursive formula for $f_n$. The pattern is that you add $t_1$ and then some factor multiplied by $k$. Now this factor gets messy and very large quickly. This factor is given by $a+ny(t_1-t_0)$ and then adding each preceding factor minus $ak$ multiplied by $y$. I know its quite a nasty summation, but I will try my luck here!
- $\begingroup$ So the number of terms in the formula increases as $n$ increases? $\endgroup$saulspatz– saulspatz2021-05-06 20:35:25 +00:00Commented May 6, 2021 at 20:35
- $\begingroup$ All the terms will always have the form $t_1+Xk$, the number of terms that the factor X consists of will increase. I see that the formating was a bit poor because of the long equation, I will try to fix that! $\endgroup$matte_studenten– matte_studenten2021-05-06 20:50:00 +00:00Commented May 6, 2021 at 20:50
- 1$\begingroup$ No, I think the formatting is fine. I just wanted to be sure I understood. $\endgroup$saulspatz– saulspatz2021-05-06 20:58:51 +00:00Commented May 6, 2021 at 20:58
2 Answers
We can simplify your formula quite a bit, but it doesn't result in a recurrence that I know how to solve. We have $$\begin{align} f_n&=t_1+k\left( a+ny(t_1-t_0)+y\sum_{i=1}^{n-1} (f_i-t_1-ak) \right)\\ &=t_1+ka+kny(t_1-t_0)+ky\sum_{i=1}^{n-1}f_i-ky(n-1)(t_1+ak)\\ &=t_1+ka+n(ky)(t_1-t_0)-n(ky)(t_1+ak)+ky(t_1+ak)+ky\sum_{i=1}^{n-1}f_i\\ &=\alpha+n\beta+ky\sum_{i=1}^{n-1}f_i \end{align}$$ where $$\begin{align} \alpha&=t_1+ak+ky(t_1+ak)\\ \beta &=-ky(t_0+ak) \end{align}$$
if I haven't made any mistakes.
This is easier to compute with and think about, but I don't see any way to get an explicit formula for $f_n$. I had hoped we might end up with a recursive formula for $\sum f_i$, but the coefficient of $ky$ seems to exculde any possibility of that.
This really should be a comment, not an answer, but I have no hope of typing it in a comment box.
- $\begingroup$ In the third row counting from where the equations begin, you have a $-ky(t_1+ak)$, shouldn't it be $+ky(t_1+ak)$ $\endgroup$matte_studenten– matte_studenten2021-05-07 13:14:45 +00:00Commented May 7, 2021 at 13:14
- 1$\begingroup$ @alibakly Yes, I think you're right. I'll change it. Thanks. $\endgroup$saulspatz– saulspatz2021-05-07 13:24:54 +00:00Commented May 7, 2021 at 13:24
Starting from Saulspatz answer: $$ f_n = \alpha+n\beta+ky\sum_{i=1}^{n-1}f_i \\\Leftrightarrow\\ \sum_{i=1}^{n}f_i=\frac{f_n -\alpha-n\beta+ky f_n }{ky} $$
Also, with $n\leftarrow n+1$:
$$ f_{n+1} = \alpha+(n+1)\beta+ky\sum_{i=1}^{n}f_i \\\Leftrightarrow\\ \frac{f_{n+1} -\alpha-(n+1)\beta }{ky}= \sum_{i=1}^{n}f_i $$
Substituting one equation into the other, we obtain $$ f_{n+1} = f_n·(k·y + 1) + β $$
This is a inhomogenous linear recurrence with constant coefficients, so you can compute the explicit form of $f_n$, and using that, probably the explicit form of $\sum f_n$.
- $\begingroup$ Thanks for the help! I'm not really familiar with recurrence problems so how would I go about trying to find an explicit formula for $f_n$? $\endgroup$matte_studenten– matte_studenten2021-05-07 00:34:17 +00:00Commented May 7, 2021 at 0:34
- 1$\begingroup$ You can try to repeatedly substitute the definition of the recurrence into the right side and look if you can see a pattern.Alternatively, look at $e_n := f_{n+1}-f_n$, which loses the inhomogenous part, and try to guess the explicit formula of $e_n$. Then use $f_{n+1} = f_0 + \sum_{i=0}^n e_n$ $\endgroup$Sudix– Sudix2021-05-07 00:43:06 +00:00Commented May 7, 2021 at 0:43
- 1$\begingroup$ I now see that \begin{align} f_n=\gamma \phi^{n-1} -\beta( \phi^{n-2}+...\phi^2+\phi+1),\end{align} which with a geometric sum gives \begin{align} f_n=\gamma \phi^{n-1} -\beta \frac{1-\phi^{n-1}}{1-\phi}\end{align} $\endgroup$matte_studenten– matte_studenten2021-05-07 12:40:50 +00:00Commented May 7, 2021 at 12:40
- 2$\begingroup$ Just a small remark: in your last equation you have:$$ f_{n+1} = f_n·(k·y + 1) - β. $$ Shouldn't it be $$ f_{n+1} = f_n·(k·y + 1) + β \;? $$ $\endgroup$matte_studenten– matte_studenten2021-05-07 13:29:56 +00:00Commented May 7, 2021 at 13:29
- 2$\begingroup$ This is what I was trying to do yesterday. I can't believe I couldn't make it work. $\endgroup$saulspatz– saulspatz2021-05-07 13:38:34 +00:00Commented May 7, 2021 at 13:38