9
$\begingroup$

I'm pondering the following sequence:

$$\begin{equation} \begin{split} a_1 & = b \\ a_{n+1} & = c\frac{1}{n}\sum_{k=1}^{n}a_k = c \times \text{mean of } \{a_1,\dots,a_n\} \end{split} \end{equation}$$

For example, setting $b=1,c=1/2$, the sequence goes

$$1, \frac{1}{2}, \frac{3}{8}, \frac{5}{16}, \frac{35}{128}, \frac{63}{256}, \frac{231}{1024}, \frac{429}{2048}, \frac{6435}{32768}, \frac{12155}{65536}, \frac{46189}{262144}, \dots$$


Does the general term $a_n=a(n,b,c)$ of this sequence have a closed form in terms of $b$ and $c$? Closed forms do exist for some values of $c$:

$$\begin{equation} \begin{split} a(n,b,2) & = nb \\ a(n,b,3) & = \frac{n(n+1)}{2}b \end{split} \end{equation}$$

Since those formulae contain the closed-form expressions for the sums of the $0$th and $1$st powers of the first $n$ integers, one might be tempted to assume

$$a(n,b,4) \stackrel{\text{?}}{=} \frac{n(n+1)(2n+1)}{6}b$$

in analogue with the formula for the sum of squares. However, this turns out to be false.

$\endgroup$
  • 2
    $\begingroup$ @BrianM.Scott OP is correct: $a(n,b,4) = \binom{n+4-2}{4-1}b = \frac{n(n+1)(n+2)}{6} \neq \frac{n(n+1)(2n+1)}{6}$ for $n>1.$ $\endgroup$ – David K Dec 18 '14 at 14:26
  • 1
    $\begingroup$ @David: Yes, I read the OP's generalization and thought mine. sigh $\endgroup$ – Brian M. Scott Dec 18 '14 at 19:01
7
$\begingroup$

The recurrence is equivalent to $$ a_{n+1}=\frac{\left(n-1\right)a_{n}+ca_{n}}{n}=\frac{c+n-1}{n}a_{n}. $$ This expression for the running mean (modulo the $c$ term) is used in numerical analysis for stability reasons. This recurrence has solution $$ a_{n+1}=\frac{b\left(c\right)_{n}}{n!} $$ where $\left(\cdot\right)_{n}$ is the Pochhammer symbol (a.k.a. rising factorial).


To verify this expression's correctness, here's Wolfram computing your answers using the formula above for $b=1,c=1/2$:

enter image description here

$\endgroup$
  • 3
    $\begingroup$ An alternative statement of the same formula when $c$ is an integer: $a_n = \binom{c+n-2}{n-1} b.$ $\endgroup$ – David K Dec 18 '14 at 8:55
  • $\begingroup$ The form above also reveals that if $c$ is a negative integer, there are only finitely many nonzero terms in the sequence. $a_n=0$ for all $n > \left|c\right|$. $\endgroup$ – parsiad Dec 18 '14 at 18:36
  • $\begingroup$ Also arguably interesting: $$ \lim a_{n}=\begin{cases} 0 & \text{if }c<1\\ b & \text{if }c=1\\ \infty & \text{if }c>1 \end{cases} $$ $\endgroup$ – parsiad Jan 11 '15 at 0:11

Your Answer

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