# recursive function: non-recursive form possible?

Can the following recursive function be converted to a non-recursive form?

$$f(x,c,\ell)=\frac{c-c^\ell}{1-c}+(c-2)\sum \limits_{k=1}^{\ell-1}f(x,c,k)$$

$$f(x,c,1)=c$$

$$c= \text{constant}$$

$$\ell=\text{length}$$

If so, where do I start?

• What is the role played by $x$? It is easy to see by induction that, since $f(x,c,1)$ is constant in $x$, also $f(x,c,\ell)$ is constant in $x$ for every $\ell$. – Hugo Feb 27 '16 at 1:48
• Perhaps I have made it more complicated than it need be, so should be: $f(c,\ell)=\frac{c-c^\ell}{1-c}+(c-2)\sum_{k=1}^{\ell-1}f(c,k)$ – Gerard Feb 27 '16 at 2:25
• EDIT: I claim $f(c,\ell)=c^\ell - c(c-1)^\ell$ for every $\ell \geq 3$. I am trying to fix the details of induction... – Hugo Feb 27 '16 at 2:35

I use $n$ instead of $\ell$, hope you do not mind. Let's prove by (strong) induction that, for $n \geq 2$, it holds $f(c,n) = c^n - c(c-1)^{n-2}$. For $n=2$ it is clear, since $f(c,2) = c+(c-2)c = c^2-c$. If the assumption holds for every $2 \leq j \leq n$, then \begin{align*} f(c,n+1) &= \frac{c^{n+1}-c}{c-1} + (c-2)\sum_{j=1}^n f(c,j) = \frac{c^{n+1}-c}{c-1} + (c-2)\left [ \sum_{j=2}^n \left (c^j - c(c-1)^{j-2}\right ) + c \right ] \\ &= \frac{c^{n+1}-c}{c-1} + (c-2)\sum_{j=2}^n c^j -c(c-2)\sum_{j=2}^n (c-1)^{j-2} + (c-2)c \\ &= \frac{c^{n+1}-c}{c-1} + (c-2)\sum_{j=0}^n c^j -(c-2)(1+c) - c(c-2)\sum_{j=0}^{n-2} (c-1)^j + (c-2)c \\ &= \frac{c^{n+1}-c}{c-1} + (c-2)\frac{c^{n+1}-1}{c-1} - c(c-2)\frac{(c-1)^{n-1}-1}{c-2} -c+2 \\ &= \frac{c^{n+1}-c+c^{n+2}-2c^{n+1}-c+2+2c-2}{c-1} - c(c-1)^{n-1} = c^{n+1} - c(c-1)^{n-1}. \end{align*}
• $f(c,n+1)=\frac{c^{(n+1)}-c}{1-c}+(c-2)\sum_{j=2}^nf(c,n)$ – Gerard Feb 27 '16 at 14:44
• $f(c,n+1)=\frac{c^{(n+1)}-c}{c-1}+(c-2)(\frac{c^n-1}{c-1}+(c-2)\sum_{j=2}^{n-1}f(c,j))$ – Gerard Feb 27 '16 at 14:51
• In the induction of course I used for $f(c,j)$ the expression $c^j-c(c-1)^{j-2}$ (induction hypothesis). But for $j=1$ this does not hold, so I added the term $(c-2)c$. I will try to edit the answer and make it clearer. – Hugo Feb 27 '16 at 16:17