4
$\begingroup$

In a project of mine I came across the recurrence relation $$ a_{n+1} = 1 -(n+1)\sum_{k=1}^n{\frac{a_k}{n-k+1}\binom{n}{k}},\quad a_1=2; $$

From calculating the first few terms it seems obvious that $$ a_n = (-1)^{n+1}(n+1),\quad n\geqslant2, $$ and, once guessed, this solution can be verified by induction.

My question is if there is an easy way to arrive at this solution without guessing. Generating functions work but seem unnecessarily unwieldy for such an easy-looking recurrence.

$\endgroup$
1
  • 1
    $\begingroup$ You can clean up the expression to write it as a single binomial convolution equal to zero. Then you have the option to use exponential generating functions or interpret it as iterated difference operator application or interpret it as a convolution and write the inverse to get the result. $\endgroup$ – Phira Dec 29 '13 at 17:17
3
$\begingroup$

With $a_0=-1$, your recurrence becomes

$$\sum_{k=0}^na_k\binom nk =f(n)=\begin{cases}-1 &\text{ if $n=0$,}\\ 1 &\text{ if $n=1$,}\\ 0 &\text{ if not.}\end{cases}$$

This implies the inverse relation $$a_n=\sum_{k=0}^n(-1)^{n-k}\binom{n}kf(k)=(-1)^{n}(-1)+(-1)^{n-1}n =(-1)^{n+1}(n+1)$$ as desired.

$\endgroup$
1
$\begingroup$

$$ a_{n+1} = 1-\sum_{k=1}^n{\binom{n+1}{k}a_k} $$ maybe use formula $$\sum_{k=1}^n{(-1)^k k\binom{n}{k}}=0$$

$\endgroup$

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.