Is there a closed form for this recursion equation?

Question

Given $$f(a)=\frac{1}{6} \sum _{i=1}^6 \left[1-(1-f (a-1)) \left(\frac{i}{6}\right)^a\right]$$ with $f(1)=0$, $a\in\mathbb{N}$ and $f:\mathbb{N}\to\mathbb{Q},$

is there a way to write a closed form solution for the above recursion function. I am conducting a research and obtained the above result, but was interested if a function of $f(a)$ only in terms of $a$ exists, for arbitrary $a$. This would save a lot of computational work for my research. This in fact, is a small result which will be used in more complex calculations, therefore a closed form would be optimal. Thank you.

Answer 1

We have to study the recursion

$$f(a) = \frac{1}{6} \sum_{i=1}^{6}\left( 1-\left( 1-f(a-1) \right)(\frac{i}{6})^a \right)\tag{0}$$

Letting

$$g(a) = \frac{1}{6}\sum_{i=1}^{6} (\frac{i}{6})^a\tag{1}$$

the recursion reads

$$f(a) = 1-g(a) + g(a) f(a-1), f(1) = 0, a=2, 3, ...\tag{2}$$

Is is a linear inhomogenous recursion relation which can be solved by standard methods.

This means that the general solution is gven by the sum of the general solution to the homogeneous equation and one special solution to the inhomogeneous equation.

Now the homogenous equation

$$f(a) = g(a) f(a-1)\tag{3}$$

is easily solved generally by

$$f_h(a) = c \prod_{m=1}^{a-1} g(1+m)\tag{4}$$

here $c$ is an arbitrary constant.

We can find a special solution to the inhomogeneous equation $(2)$ using a trick called variation of the constant ($c$) (which can be easily found on the internet) applied to the expression $(4)$

Doing this carefully the solution is finally found to be

$$f_{s}(a) = \left(\prod _{m=0}^{a-1} g(m+1)\right) \left(\sum _{n=-1}^{a-1} \frac{1-g(n+1)}{\prod _{m=0}^n g(m+1)}-\frac{5}{7}\right)\tag{5}$$

Shifting indices and noticing that $g(0)=1$ this can be written more elegantly as

$$f_{s}(a) = \left(\prod _{m=1}^{a} g(m)\right) \left(\sum _{n=1}^{a} \frac{1-g(n)}{\prod _{m=1}^{n} g(m)}-\frac{5}{7}\right)\tag{5a}$$

Expression $(5a)$ is similar to that of Raffaele.

To derive $(5)$ we have used that

$$g(0) = 1, g(1) = \frac{7}{12}\tag{6}$$

Checking $f_{s}(1)=0$:

The second factor in $f_{s}(a)$ vanishes because

$$\sum _{n=-1}^{a-1} \frac{1-g(n+1)}{\prod _{m=0}^n g(m+1)}=\left(\frac{1-g(n+1)}{\prod _{m=0}^n g(m+1)}\text{/.}\, n\to -1\right)+\left(\frac{1-g(n+1)}{\prod _{m=0}^n g(m+1)}\text{/.}\, n\to 0\right)=0+\frac{5}{7}$$

Checking $f_{s}(2) = \frac{125}{216}$: OK

In fact from the original recusion $(0)$ we get

$$f(2)=\frac{1}{6} \left(-\frac{1}{36} 41 (1-f(1))+\frac{7}{18} (f(1)-1)+f(1)+5\right)\text{/.}\, f(1)\to 0=\frac{125}{216}$$

which conincides with $f_{s}(2)$.

Discussion

As noticed in the solution of Jean-Claude Arbaut my formula $(5a)$ can be transformed into this much simpler expression:

$$f(a) = 1 - \prod_{k=2}^{a} g(k)\tag{5b}$$

Noticing also that we can write

$$g(k) = \frac{1}{6^{k+1}} H_6^{(-k)}\tag{5c}$$

where $H_n^{(m)}$ is the harmonic number of order $m$ we get from $(5b)$ that

$$f(a) = 1-6^{\frac{1}{2} \left(-a^2-3 a+4\right)} \prod _{k=2}^a H_6^{(-k)}\tag{5d}$$

so that $f$ is expressed in terms of known (but higher trancendental) functions.

Answer 2

Let's call $\varphi(k)=6^{-k-2} \left(1+2^{k+1}+2^{2 k+2}+3^{k+1}+5^{k+1}+6^{k+1}\right)$

and $\gamma(h)=6^{-h-2} \left(1+2^{h+1}+2^{2 h+2}+3^{h+1}+5^{h+1}-5\ 6^{h+1}\right)$

Then we have

$$f(a)= \left(\prod _{k=1}^{a-1} \varphi(k)\right) \sum _{h=0}^{a-1} \left(-\frac{\gamma(h)}{\prod _{k=1}^h \varphi(k)}\right)-\frac{5}{12} \prod _{k=1}^{a-1} \varphi(k)$$

first values are $$\left(0,\frac{125}{216},\frac{26645}{31104},\frac{231720479}{241864704},\frac{3720223313533}{3761479876608},\ldots\right)$$

Answer 3

Your recurrence can be written, with $v(a)=1-f(a)$,

$$v(a)=v(a-1)\frac16\sum_{i=1}^6\left(\frac{i}{6}\right)^a$$

And $v(1)=1$.

This leads immediately to:

$$f(a)=1-\frac{1}{6^{a-1}}\prod_{k=2}^{a}\left[\left(\frac{1}{6}\right)^{k} +\left(\frac{2}{6}\right)^{k}+\left(\frac{3}{6}\right)^{k}+\left(\frac{4}{6}\right)^{k}+\left(\frac{5}{6}\right)^{k}+\left(\frac{6}{6}\right)^{k} \right]$$

Not sure it qualifies as a "closed form", but I suspect you can't do much better. If the problem is performance, notice that you can improve it very much by keeping all preceding values of $f(a)$ in memory. Then computing the next one simply requires applying your recurrence, which is not difficult to compute. Notice also that $f(a)$ converges to $1$ linearly.