I am stuck while trying to solve a recurrence relation. I just need the characteristic function to know the dependence of $Y_n$.

My recurrence relation is of the following form where $a$ and $b$ are constant,

$Y_n = a + b \frac{\sum_{j=1}^{n-1}Y_j}{n-1}$

I am unable to figure out the characteristic equation or even the asymptotic nature of the series.

  • $\begingroup$ @Peter $x^n$ seems to work but the $n$ in the denominator doesn't add up. It seems to me that there is something missing. $\endgroup$ – learner Jan 27 '17 at 17:40
  • $\begingroup$ I suppose, that $n$ is unknown, but fixed. So, we will get a polynomial with coefficients depending on the degree. $\endgroup$ – Peter Jan 27 '17 at 17:43
  • $\begingroup$ $n$ is known, the second term of the recurrence relation just means taking a mean over the previous terms. $\endgroup$ – learner Jan 27 '17 at 17:45
  • $\begingroup$ For any concrete $n$, we have concrete coefficients and can determine the characteristic equation as usual. $\endgroup$ – Peter Jan 27 '17 at 17:46
  • $\begingroup$ $n$ is the sequence index. It is not fixed. This is not a simple linear recurrence, so it does not have a characteristic equation. Characteristic equations occur for recurrences of the form $y_n = f(y_{n-1}, ..., y_{n-k})$ for some fixed $f$. You do not have that here. Your recurrence involves all previous elements of the sequence, not a fixed number of them. The standard linear methods do not apply. I suggest looking that the sequence $X_n = \sum_{j=1}^{n} Y_j$ instead. Once you have it, finding $Y_n$ from it is easy. $\endgroup$ – Paul Sinclair Jan 27 '17 at 18:35

Using the definition of $X_n$ in the comments by @Paul Sinclair, I ran out the first couple of cases, and then used the Online Encyclopedia of Integer Sequences to formulate the following conjecture: $$X_n = \frac{1}{(n-1)!}\left[\displaystyle\sum_{i=0}^{n-2} \left(ab^i\sum_{j=i+2}^{n} s(n,j)\right)+X_1\prod_{i=1}^{n-1}(b+i)\right]$$ where $s(n,k)$ is the unsigned Stirling number of the first kind.

Using the recurrence relation $X_{n+1}=a+\frac{n+b}{n}X_n$ given by Paul Sinclair, it is an interesting exercise to prove the formula using induction.


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.