1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Hugo Feb 27 '16 at 1:48
  • $\begingroup$ 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)$ $\endgroup$ – Gerard Feb 27 '16 at 2:25
  • $\begingroup$ 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... $\endgroup$ – Hugo Feb 27 '16 at 2:35
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks, I am trying to understand the induction, but I get something quote different: $\endgroup$ – Gerard Feb 27 '16 at 14:38
  • $\begingroup$ $f(c,n+1)=\frac{c^{(n+1)}-c}{1-c}+(c-2)\sum_{j=2}^nf(c,n)$ $\endgroup$ – Gerard Feb 27 '16 at 14:44
  • $\begingroup$ $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))$ $\endgroup$ – Gerard Feb 27 '16 at 14:51
  • $\begingroup$ 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. $\endgroup$ – Hugo Feb 27 '16 at 16:17
  • $\begingroup$ Considering c=14 and n=3, f(c,n)=378: $\endgroup$ – Gerard Feb 28 '16 at 13:31

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.