# Prove $\{a_n\}$, where $\sum_{k=0}^{n}\binom n k a_ka_{n-k}=a_n^2$ is a geometric progression

Let $\{a_n\}$, $n \geqslant 0$, be a sequence of positive real numbers satisfying $\sum_{k=0}^{n}\binom n k a_ka_{n-k}=a_n^2$. Prove that $\{a_n\}$ is a geometric progression.

I have tried to consider the ratio of two consecutive terms, and apply Pascal's identity, but to no avail, as I do not know how to deal with the changes to the limits of the sum caused by the use of this identity. Are there any good methods for solving the above?

• First of all $a_1 = 2a_0$ so if it's a geometrical progression it has to be on the form $a_n = c 2^n$. Assuming this for induction and use the binomial theorem. – Winther Jul 11 '17 at 12:57
• Induction works. Assume $a_n=a r^n$ and compute $a_n^2$. – B. Goddard Jul 11 '17 at 12:58
• Of course! Thank you. – wrb98 Jul 11 '17 at 13:01

Note that $a_1^2 = \binom{1}{0}a_1a_0 + \binom 11 a_0a_1 = 2a_0a_1$. This makes $a_0 = \frac 12a_1$.

Similarly,$a_2^2 = a_2a_0 + 2a_1^2 + a_0a_2 = 2a_0a_2 + 8a_0^2 \implies a_2 = 4a_0$.

Therefore, it's enough to prove that $a_n = \frac{a_{n+1}}{2}$, or in other words, that $a_n = 2^n a_0$.

To do this, note that the base case is done, and the induction step is: $$a_n^2 = \sum_{k=0}^n \binom nk a_{n-k}a_k = \sum_{k=1}^{n-1} \binom nk 2^{n-k}2^k a_0^2 + 2a_na_0 = a_0^2 \left(\sum_{k=1}^{n-1} \binom{n}{k}2^n\right) + 2a_na_0 \\ = a_0^2 (2^n-2)2^n + 2a_na_0$$

From here, I leave you to see that $a_n = 2^na_0$. Hence, the induction is complete.

By induction we prove that $a_k = b2^k$.

Base: $a_0^2 = \binom{0}{0}a_0^2 = b^2$

IH: $a_n = b2^n$

\begin{align}a_{n+1}^2 &= \sum_{k=0}^{n+1}\binom{n+1}{k}a_ka_{n+1-k} \\ &= ba_{n+1} + \sum_{k=1}^{n}\binom{n+1}{k}b2^kb2^{n+1-k} + ba_{n+1} \\ &= 2ba_{n+1} + b^22^{n+1}(2^{n+1}-2)\end{align}

$$\implies a_{n+1}^2-2ba_{n+1} = (b2^{n+1})^2 - 2b(b2^{n+1})$$

$a_{n+1} = b2^{n+1}$

Assuming that $a_n$ is a geometric progression, then $a_ka_{n-k}$ does not depend on $k$. So $$a_n^2 = \sum_{k=0}^{n}\binom n k a_ka_{n-k} = a_0a_n\sum_{k=0}^{n}\binom n k = a_0 a_n 2^n.$$ Since $a_n$ is nonzero, we divide both sides by it to get $a_n = a_02^n$ which is a geometric progression and we have just shown it satisfies the original equation.

• This argument only shows that $a_n$ can be a geometrical progression. The question is to prove that $a_n$ has to be a geometrical progression. – Winther Jul 11 '17 at 13:41
• The assumption is used to find $a_n=a_02^n$. Now the same steps in reverse show it is a solution as expected. – Somos Jul 11 '17 at 13:44
• You are assuming the conclusion. If the recurrence had another solution then you would not find it this way. For example if you run the exact same argument on the problem of proving that $\sum_{k=0}^n{n\choose k} a_k a_{n-k} = 2^n$ has the only solution $a_k = 1$ then you would prove this. However this would give a false conclusion as this recurrence has infinitely many solutions. – Winther Jul 11 '17 at 14:34
• (small mistake in the comment above, I meant $\sum_{k=0}^n{n\choose k}a_kb_{n-k} = 2^n$ has the only solution $a_n = b_n = 1$) – Winther Jul 11 '17 at 14:43
• But that is a different problem, isn't it? – Somos Jul 11 '17 at 16:13