Summation and factorial.

Question

If $$2^{n}a_{n}=\sum_{k=0}^{n}{a_{k}a_{n-k}},\phantom{a}\forall n\in\mathbb{N},$$ with $a_{0}=1,$ then $$a_{n}=\dfrac{a_{1}^{n}}{n!},\phantom{a}\forall n\in\mathbb{N}.$$

Attempt: Notice that

(1) For $ n=2t + 1, $ we have $$2^{2t+1}a_{2t+1}=2(a_{0}a_{2t+1}+a_{1}a_{2t}+a_{2}a_{2t-1}+\cdots+a_{t-1}a_{t+2}+a_{t}a_{t+1}).$$ Then \begin{align} (2^{2t}-1)a_{2t+1}&=a_{1}a_{2t}+a_{2}a_{2t-1}+\cdots+a_{t-1}a_{t+2}+a_{t}a_{t+1}\\ &=a_{1}^{2t+1}\left(\dfrac{1}{(2t)!}+\dfrac{1}{2!(2t-1)!}+\cdots+\dfrac{1}{(t-1)!(t+2)!}+\dfrac{1}{t!(t+1)!}\right)\\ &=\dfrac{a_{1}^{2t+1}}{(2t)!}\left(1+\dfrac{2t}{2!}+\cdots+\dfrac{(t+3)(t+4)\cdots(2t-1)(2t)}{(t-1)!}+\dfrac{(t+2)(t+3)(t+4)\cdots(2t-1)(2t)}{t!}\right). \end{align}

(2) For $n=2t,$ we have $$2^{2t}a_{2t}=2a_{0}a_{2t}+2a_{1}a_{2t-1}+2a_{2}a_{2t-2}+\cdots+2a_{t-1}a_{t+1}+a_{t}^{2}.$$ Then \begin{align} 2(2^{2t-1}-1)a_{2t}&=2a_{1}a_{2t-1}+2a_{2}a_{2t-2}+\cdots+2a_{t-1}a_{t+1}+a_{t}^{2}\\ &=a_{1}^{2t}\left(\dfrac{2}{(2t-1)!}+\dfrac{2}{2!(2t-2)!}+\cdots+\dfrac{2}{(t-1)!(t+1)!}+\dfrac{1}{t!t!}\right)\\ &=\dfrac{a_{1}^{2t}}{(2t-1)!}\left(2+\dfrac{2(2t-1)}{2!}+\cdots+\dfrac{2(t+2)(t+3)\cdots(2t-1)}{(t-1)!}+\dfrac{(t+1)(t+2)(t+3)\cdots(2t-1)}{t!}\right). \end{align}

Is there a formula to reduce the above expressions?

Any hints would be appreciated.

Answer 1

The generating function approach in my other answer does not require knowing the desired formula ahead of time, but I understand that you are not familiar with generating functions. Maybe just treat that answer as an example of why generating functions are useful.

Mathematical induction looks like it would be messy because $n$ appears in both the summand and the upper limit of summation.

Instead, here is an alternative approach. We have a recurrence relation and a proposed formula. To prove that the formula is correct, we need only show that it satisfies the recurrence relation. First check the boundary condition ($n=0$): $$a_1^0/0! = 1 = a_0,$$ so that checks out. Now check the main recurrence by substituting the proposed formula: $$\sum_{k=0}^n a_k a_{n-k} = \sum_{k=0}^n \frac{a_1^k}{k!} \frac{a_1^{n-k}}{(n-k)!} = \frac{a_1^n}{n!}\sum_{k=0}^n \binom{n}{k}=\frac{a_1^n}{n!}2^n=2^n a_n,$$ and we are done.

(The sum $\sum_k \binom{n}{k} = 2^n$ is well known and follows from the binomial theorem or by counting subsets of $\{1,\dots,n\}$ according to their cardinality $k$.)

Answer 2

The sum is a convolution of $a_n$ with itself, so the generating function of the RHS is $A(z)^2$, where $A(z)=\sum_n a_n z^n$ is the generating function of $a_n$. The generating function of $2^n a_n$ is $A(2z)$, so we have $A(2z)=A(z)^2$. Hence $A(z)=\exp(c z)$ for some constant $c$, which implies that $a_n=c^n/n!$. Now evaluate at $n=1$ to obtain $a_1=c^1/1!=c$, so $a_n=a_1^n/n!$.