Kvant Math Problem 148
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m54s
Source on kvant.digital
Problem
The sequence $x_0$, $x_1$, $x_2$, $\ldots$ is defined by the following conditions: $x_0=1$, $x_1=\lambda$, for any $n\gt1$ $$(\alpha+\beta)^n x_n=\alpha^n x_n x_0+\alpha^{n-1}\beta x_{n-1} x_1+\alpha^{n-2}\beta^2 x_{n-2} x_2+\ldots+\beta^n x_0 x_n.$$ Here $\lambda$, $\alpha$, $\beta$ are given positive numbers. Find $x_n$ and determine for which $n$ the quantity $x_n$ attains its greatest value.
A. L. Lopshits
Exploration
Let
$$F_n=(\alpha+\beta)^n x_n .$$
The defining relation becomes
$$F_n=\sum_{k=0}^{n}\alpha^{,n-k}\beta^k x_{n-k}x_k .$$
The right-hand side is a convolution. Such recurrences are usually attacked by generating functions.
Before introducing them, compute the first terms.
For $n=1$,
$$(\alpha+\beta)x_1=\alpha x_1x_0+\beta x_0x_1,$$
which is an identity.
For $n=2$,
$$(\alpha+\beta)^2x_2 =(\alpha^2+\beta^2)x_2+2\alpha\beta x_1^2,$$
hence
$$2\alpha\beta x_2=2\alpha\beta \lambda^2, \qquad x_2=\lambda^2.$$
For $n=3$,
$$(\alpha+\beta)^3x_3 =(\alpha^3+\beta^3)x_3 +3\alpha^2\beta x_2x_1 +3\alpha\beta^2 x_1x_2.$$
Since $x_2=\lambda^2$,
$$3\alpha\beta(\alpha+\beta)x_3 = 3\alpha\beta(\alpha+\beta)\lambda^3,$$
so
$$x_3=\lambda^3.$$
This strongly suggests
$$x_n=\lambda^n.$$
To test the conjecture, substitute it into the recurrence:
$$\sum_{k=0}^{n}\alpha^{n-k}\beta^k\lambda^{n-k}\lambda^k = \lambda^n\sum_{k=0}^{n}\alpha^{n-k}\beta^k.$$
Since
$$\sum_{k=0}^{n}\alpha^{n-k}\beta^k = \frac{\alpha^{n+1}-\beta^{n+1}}{\alpha-\beta},$$
this equals $(\alpha+\beta)^n\lambda^n$ only in special cases, so direct substitution does not prove anything. The coincidence for $n=2,3$ must come from the recurrence itself.
Let
$$G(t)=\sum_{n\ge0}x_n t^n .$$
Multiplying the recurrence by $t^n$ and summing for $n\ge0$,
$$\sum_{n\ge0}(\alpha+\beta)^n x_n t^n = \sum_{n\ge0}\sum_{k=0}^{n} \alpha^{n-k}\beta^k x_{n-k}x_k t^n .$$
The left side is $G((\alpha+\beta)t)$. The right side factors:
$$G(\alpha t)G(\beta t).$$
Hence
$$G((\alpha+\beta)t)=G(\alpha t)G(\beta t).$$
Together with
$$G(0)=1,\qquad G'(0)=x_1=\lambda,$$
this functional equation should determine $G$.
Write $H(t)=\log G(t)$. Then
$$H((\alpha+\beta)t)=H(\alpha t)+H(\beta t).$$
If
$$H(t)=\sum_{m\ge1} c_m t^m,$$
then
$$c_m\bigl((\alpha+\beta)^m-\alpha^m-\beta^m\bigr)=0.$$
For $m\ge2$,
$$(\alpha+\beta)^m>\alpha^m+\beta^m$$
because $\alpha,\beta>0$. Hence $c_m=0$ for all $m\ge2$. Thus
$$H(t)=c_1 t=\lambda t,$$
and
$$G(t)=e^{\lambda t}.$$
Therefore
$$x_n=\frac{\lambda^n}{n!}.$$
Checking:
$$x_2=\frac{\lambda^2}{2},$$
which indeed satisfies the recurrence, so the earlier computation missed the factor $2$ coming from the coefficient of $x_2$.
Now determine the maximum of $x_n$. Since
$$\frac{x_{n+1}}{x_n} = \frac{\lambda}{n+1},$$
the sequence increases while $n+1<\lambda$ and decreases while $n+1>\lambda$. The maximum occurs at the transition.
The delicate point is the uniqueness of the generating function solution. The logarithmic argument gives it because $G(0)=1$.
Problem Understanding
We are given positive numbers $\alpha,\beta,\lambda$ and a sequence $(x_n)$ with
$$x_0=1,\qquad x_1=\lambda,$$
and for every $n\ge1$,
$$(\alpha+\beta)^n x_n = \sum_{k=0}^{n} \alpha^{,n-k}\beta^k x_{n-k}x_k.$$
The task is to determine all terms $x_n$ and then find for which indices $n$ the sequence attains its greatest value.
This is a Type C problem. We must determine the sequence explicitly and then identify the index or indices at which its maximum is attained.
The core difficulty is to solve the nonlinear convolution recurrence. The natural idea is to convert the convolution into a product by means of a generating function.
The answer will be
$$x_n=\frac{\lambda^n}{n!},$$
and the maximum is governed by the ratio
$$\frac{x_{n+1}}{x_n}=\frac{\lambda}{n+1}.$$
Proof Architecture
Define the generating function $G(t)=\sum_{n\ge0}x_n t^n$; summing the recurrence yields the functional equation $G((\alpha+\beta)t)=G(\alpha t)G(\beta t)$.
Since $G(0)=1$, the logarithm $H(t)=\log G(t)$ is a formal power series; substituting into the functional equation gives $H((\alpha+\beta)t)=H(\alpha t)+H(\beta t)$.
If $H(t)=\sum_{m\ge1}c_m t^m$, then comparison of coefficients yields
$$c_m\bigl((\alpha+\beta)^m-\alpha^m-\beta^m\bigr)=0.$$
Because $\alpha,\beta>0$, the factor in parentheses is positive for every $m\ge2$; hence all $c_m$ with $m\ge2$ vanish.
The coefficient $c_1$ equals $G'(0)=\lambda$, so $H(t)=\lambda t$ and therefore $G(t)=e^{\lambda t}$.
Extracting coefficients gives $x_n=\lambda^n/n!$.
The maximum is obtained by analyzing the ratio $x_{n+1}/x_n=\lambda/(n+1)$.
The most delicate lemma is the deduction that all coefficients $c_m$ with $m\ge2$ vanish.
Solution
Let
$$G(t)=\sum_{n=0}^{\infty}x_n t^n.$$
The defining recurrence can be written as
$$(\alpha+\beta)^n x_n = \sum_{k=0}^{n} \alpha^{,n-k}\beta^k x_{n-k}x_k.$$
Multiply both sides by $t^n$ and sum over all $n\ge0$. The left-hand side becomes
$$\sum_{n=0}^{\infty}(\alpha+\beta)^n x_n t^n = G((\alpha+\beta)t).$$
For the right-hand side,
$$\sum_{n=0}^{\infty} \sum_{k=0}^{n} \alpha^{,n-k}\beta^k x_{n-k}x_k t^n = \left(\sum_{m=0}^{\infty}x_m(\alpha t)^m\right) \left(\sum_{k=0}^{\infty}x_k(\beta t)^k\right),$$
hence
$$G((\alpha+\beta)t)=G(\alpha t)G(\beta t).$$
Since $x_0=1$,
$$G(0)=1.$$
Therefore the formal logarithm
$$H(t)=\log G(t)$$
is well defined. Taking logarithms of the functional equation gives
$$H((\alpha+\beta)t)=H(\alpha t)+H(\beta t).$$
Write
$$H(t)=\sum_{m=1}^{\infty}c_m t^m.$$
Substituting this expansion yields
$$\sum_{m=1}^{\infty} c_m(\alpha+\beta)^m t^m = \sum_{m=1}^{\infty} c_m\alpha^m t^m + \sum_{m=1}^{\infty} c_m\beta^m t^m.$$
Comparing coefficients of $t^m$,
$$c_m\bigl((\alpha+\beta)^m-\alpha^m-\beta^m\bigr)=0.$$
For $m\ge2$,
$$(\alpha+\beta)^m = \alpha^m+\beta^m+ \sum_{j=1}^{m-1}\binom{m}{j}\alpha^j\beta^{m-j}.$$
Because $\alpha,\beta>0$, every term in the sum is positive. Hence
$$(\alpha+\beta)^m-\alpha^m-\beta^m>0, \qquad m\ge2.$$
Consequently,
$$c_m=0, \qquad m\ge2.$$
Thus
$$H(t)=c_1 t.$$
Now
$$G'(0)=x_1=\lambda.$$
Since $G(t)=e^{H(t)}$,
$$G'(0)=H'(0)=c_1.$$
Therefore $c_1=\lambda$, and
$$H(t)=\lambda t.$$
Hence
$$G(t)=e^{\lambda t} = \sum_{n=0}^{\infty}\frac{\lambda^n}{n!}t^n.$$
Comparing coefficients gives
$$x_n=\frac{\lambda^n}{n!}.$$
It remains to determine where this sequence is maximal.
For every $n\ge0$,
$$\frac{x_{n+1}}{x_n} = \frac{\lambda}{n+1}.$$
If $n+1<\lambda$, then $x_{n+1}>x_n$.
If $n+1>\lambda$, then $x_{n+1}<x_n$.
Thus the sequence increases up to the point where $n+1$ reaches $\lambda$, and decreases afterwards.
Let $m=\lfloor\lambda\rfloor$.
If $\lambda\notin\mathbb Z$, then
$$m<\lambda<m+1,$$
so
$$x_0<x_1<\cdots<x_m>x_{m+1}>x_{m+2}>\cdots,$$
and the unique maximum is attained at $n=m$.
If $\lambda=m$ is an integer, then
$$\frac{x_m}{x_{m-1}}=\frac{m}{m}=1,$$
so $x_m=x_{m-1}$, while
$$x_{m-1}>x_{m-2}, \qquad x_{m+1}<x_m.$$
Hence the maximum is attained exactly at the two indices $m-1$ and $m$.
Therefore
$$\boxed{,x_n=\dfrac{\lambda^n}{n!},}$$
and
$$\boxed{ \begin{cases} n=\lfloor\lambda\rfloor, & \lambda\notin\mathbb Z,\[2mm] n=\lambda-1\ \text{and}\ n=\lambda, & \lambda\in\mathbb Z. \end{cases}}$$
Verification of Key Steps
The first delicate step is the passage from the recurrence to the functional equation. The coefficient of $t^n$ in
$$G(\alpha t)G(\beta t)$$
equals
$$\sum_{k=0}^{n} (\alpha t)^{n-k}(\beta t)^k x_{n-k}x_k = t^n \sum_{k=0}^{n} \alpha^{n-k}\beta^k x_{n-k}x_k,$$
which is exactly the right-hand side of the recurrence. No coefficient is omitted and no extra factor appears.
The second delicate step is proving that $c_m=0$ for $m\ge2$. The argument depends on positivity of $\alpha$ and $\beta$. Expanding $(\alpha+\beta)^m$ by the binomial theorem gives additional positive terms
$$\binom{m}{j}\alpha^j\beta^{m-j}, \qquad 1\le j\le m-1.$$
Hence the multiplier of $c_m$ cannot vanish. Without the assumption $\alpha,\beta>0$, this conclusion would require separate analysis.
The third delicate step is locating the maximum. From
$$\frac{x_{n+1}}{x_n}=\frac{\lambda}{n+1},$$
the sign of $x_{n+1}-x_n$ is determined by whether $\lambda$ is greater or less than $n+1$. For example, if $\lambda=3.4$,
$$\frac{x_1}{x_0}=3.4,\quad \frac{x_2}{x_1}=1.7,\quad \frac{x_3}{x_2}=\frac{3.4}{3}>1,\quad \frac{x_4}{x_3}=\frac{3.4}{4}<1,$$
so the maximum occurs at $n=3=\lfloor3.4\rfloor$. If $\lambda=3$,
$$\frac{x_3}{x_2}=1,\qquad \frac{x_4}{x_3}<1,$$
and the equal maxima occur at $n=2$ and $n=3$.
Alternative Approaches
Instead of taking logarithms, one may expand
$$G(t)=1+\sum_{n\ge1}a_n t^n$$
directly in the functional equation
$$G((\alpha+\beta)t)=G(\alpha t)G(\beta t).$$
Comparing coefficients recursively shows that every $a_n$ is determined by $a_1=\lambda$. One then verifies that the coefficients of $e^{\lambda t}$ satisfy the same recursion, which forces equality of the two series.
Another approach introduces
$$y_n=n!x_n.$$
The recurrence translates into a convolution identity whose exponential generating function is again led to
$$G((\alpha+\beta)t)=G(\alpha t)G(\beta t).$$
The logarithmic method is preferable because the functional equation becomes linear after taking $\log$, and the vanishing of all higher coefficients follows immediately from coefficient comparison.