0
$\begingroup$

Let the recurrence relation

$$ a_0 = 1 \\ a_{n+1} = \frac{2 \sum_{k=0}^n a_ka_{n-k}}{n+1} $$

I need to find a close formula for this recurrence. I've noticed that $a_n = 2^n$.

I tried to prove it by induction: assuming the the statement is true for $n-1$, lets prove it for $n$:

$$a_n = \frac{2 \sum_{k=0}^n a_k a_{n-k}}{n} = \frac{2 \left( \sum_{k=0}^{n-2} a_k a_{n-k} + a_{n-1}a_1 \right)}{n} = ?$$

Somehow I need to utilize the induction assumption, but I don't know how.

$\endgroup$
3
  • $\begingroup$ You'd need to use strong induction, i.e. assume that $a_k = 2^k$ for $0\leqslant k\leqslant n$ for some $n\geqslant 0$, then show that implies $a_{n+1} = 2^{n+1}$. $\endgroup$
    – Math1000
    Commented Dec 14, 2014 at 14:26
  • $\begingroup$ You need to define $a_1$ also since $a_{0+1}$ gives dividing by zero $\endgroup$
    – kingW3
    Commented Dec 14, 2014 at 14:27
  • $\begingroup$ @kingW3, it was a typo. Now there's no dividing by zero $\endgroup$
    – AnnieOK
    Commented Dec 14, 2014 at 14:32

2 Answers 2

Reset to default
2
$\begingroup$

Let $f(z) = \sum_{n=0}^\infty a_n z^n$. Then the recurrence relation reads: $$ f^\prime(z) = 2 f(z)^2 \quad f(0) = 1 $$ which is easily solved into $f(z) = \frac{1}{1 - 2z}$. Extracting the series coefficient: $$ a_n = [z^n] \frac{1}{1 - 2z} = 2^n $$

$\endgroup$
0
$\begingroup$

$$a_{n+1}=\frac{2\sum_{k=0}^na_ka_{n-k}}{n+1}=\frac{2\sum_{k=0}^n2^k2^{n-k}}{n+1}=\frac{2\sum_{k=0}^n2^n}{n+1}=2^{n+1}$$

$\endgroup$
3
  • $\begingroup$ Please notice I've edited the relation. $\endgroup$
    – AnnieOK
    Commented Dec 14, 2014 at 14:32
  • $\begingroup$ It is a wrong solution. $\endgroup$
    – Leox
    Commented Dec 14, 2014 at 14:57
  • $\begingroup$ Why is it wrong? $\endgroup$
    – ajotatxe
    Commented Dec 14, 2014 at 21:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .