recursive function: non-recursive form possible?

Question

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?

Answer 1

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*}