CUARENTENA Problema 6

[Mórtimer]

Definimos la sucesión $(a_n)_{n\in\mathbb{N}}$ de la siguiente manera: $a_1=\frac{1}{2}$ y para todo $k$ entero positivo $$a_{2k}=\sum_{i=1}^{k-1}{a_ia_{2k-i}}+\frac{a_k^2}{2},\quad a_{2k+1}=\sum_{i=1}^{k}{a_ia_{2k+1-i}}.$$
Calcular $\sum_{i=1}^{\infty}{a_i}$.

Nota: La sucesión empieza por $\frac{1}{2}, \frac{1}{8}, \frac{1}{16}, \frac{5}{128}...$

[Mórtimer]

Solución oficial:

Spoiler: mostrar

Primero que nada, notemos que todos los términos $a_i$ son positivos (vamos a usar esto varias veces).
Notemos que se puede reescribir la recurrencia como
$$2a_n=\sum_{i=1}^{n-1}{a_ia_{n-i}}$$
para todo entero positivo $n$.
Denotemos por $s_n$ a la suma parcial de los primeros $n$ términos. Entonces
$$2s_n=2a_1+\sum_{j=2}^{n}{2a_j}=1+\sum_{j=2}^{n}{\sum_{i=1}^{j-1}{a_ia_{j-i}}}\leq 1+s_{n-1}^2.$$
En particular, si $s_{n-1}<1$, entonces $s_n<1$, luego por inducción $s_n<1$ para todo $n$ natural. Más aún, es claro que $s_n$ es creciente, luego tiene un límite cuando $n$ tiende a infinito. Sea $l$ este límite.
Ahora, notemos que cuando $n$ tiende a infinito la desigualdad anterior tiende a una igualdad (dado que todos los productos restantes tienden individualmente a $0$), por lo que $l$ satisface
$$2l=1+l^2$$
Luego $l=1$. De este modo, la suma requerida vale $1$.

[Gianni De Rico]

Quien de los de acá presentes dijo de entrada "Esto se hace con cuadriláteros armónicos" frente a un problema de Ibero, o "Esto se hace con Hensel" frente a un problema de selectivo, o incluso "Esto se hace con [...]" frente al P2 N2 Regional 2013. ??

Leí esto hace bastante tiempo, quedó grabado en mi memoria, siempre quise resolver un problema que lo use, y hoy por fin puedo decir que esto se hace con...

Spoiler: mostrar

Catalan

Solución:

Spoiler: mostrar

Sea $C_n=\frac{1}{n+1}\binom{2n}{n}$ el $n$-ésimo numero de Catalan, con $n\in \mathbb{N}_0$. Vamos a demostrar por inducción fuerte en $n$ que$$a_n=\frac{C_{n-1}}{2^{2n-1}}$$

Spoiler: mostrar

El caso base $n=1$ es cierto pues$$a_1=\frac{1}{2}=\frac{C_0}{2^{2-1}}=\frac{C_{1-1}}{2^{2\cdot 1-1}}$$Supongamos como hipótesis inductiva que vale para todo $k<n$, veamos que también vale para $n$.
Notemos que, por definición de los $a_n$, vale que$$2a_n=\sum \limits _{i=1}^{n-1}a_ia_{n-i}$$por hipótesis inductiva esto es$$\sum \limits _{i=1}^{n-1}\frac{C_{i-1}}{2^{2i-1}}\frac{C_{n-i-1}}{2^{2(n-i)-1}}=\sum \limits _{i=1}^{n-1}\frac{C_{i-1}\cdot C_{n-i-1}}{2^{2n-2}}$$entonces$$2^{2n-1}a_n=\sum \limits _{i=1}^{n-1}C_{i-1}\cdot C_{n-i-1}$$poniendo $j=i-1$$$2^{2n-1}a_n=\sum \limits _{j=0}^{n-2}C_j\cdot C_{n-j}$$pero por la recurrencia de Catalan tenemos que$$\sum \limits _{j=0}^{n-2}C_j\cdot C_{n-j}=C_{n-1}$$Entonces$$a_n=\frac{C_{n-1}}{2^{2n-1}}$$La inducción esta completa.

Explícitamente esta formula es$$a_n=\frac{1}{n2^{2n-1}}\binom{2(n-1)}{n-1}$$
Veamos por inducción en $k$ que$$\sum \limits _{n=1}^k\frac{\binom{2(n-1)}{n-1}}{n2^{2n-1}}=1-\frac{\binom{2k}{k}}{2^{2k}}$$

Spoiler: mostrar

El caso base $k=1$ es cierto pues ambos lados valen $\frac{1}{2}$.
Supongamos como hipótesis inductiva que vale para $k$, veamos que vale para $k+1$.
Tenemos que$$\begin{align*}\sum \limits _{n=1}^{k+1}\frac{\binom{2(n-1)}{n-1}}{n2^{2n-1}} & =\frac{\binom{2k}{k}}{(k+1)2^{2k+1}}+\sum \limits _{n=1}^k\frac{\binom{2(n-1)}{n-1}}{n2^{2n-1}} \\
& =\frac{\binom{2k}{k}}{(k+1)2^{2k+1}}+1-\frac{\binom{2k}{k}}{2^{2k}} \\
& =1-\left (\frac{\binom{2k}{k}}{2^{2k}}-\frac{\binom{2k}{k}}{(k+1)2^{2k+1}}\right ) \\
& =1-\frac{2(k+1)\binom{2k}{k}-\binom{2k}{k}}{(k+1)2^{2k+1}} \\
& =1-\frac{(2k+1)\binom{2k}{k}}{(k+1)2^{2k+1}} \\
& =1-\frac{1}{2^{2k+1}}\frac{2k+1}{k+1}\frac{2(k+1)}{2(k+1)}\binom{2k}{k} \\
& =1-\frac{1}{2^{2(k+1)}}\frac{(2k+1)(2k+2)}{(k+1)(k+1)}\binom{2k}{k} \\
& =1-\frac{1}{2^{2(k+1)}}\binom{2(k+1)}{k+1}
\end{align*}$$La inducción esta completa.

Ahora$$\lim \limits _{k\to \infty}\frac{\binom{2k}{k}}{2^{2k}}=0$$por #Stirling.
Finalmente$$\sum \limits _{n=1}^\infty \frac{\binom{2(n-1)}{n-1}}{n2^{2n-1}}=\lim \limits _{k\to \infty}\sum \limits _{n=1}^k \frac{\binom{2(n-1)}{n-1}}{n2^{2n-1}}=\lim \limits _{k\to \infty}1-\frac{\binom{2k}{k}}{2^{2k}}=1-\lim \limits _{k\to \infty}\frac{\binom{2k}{k}}{2^{2k}}=1-0=1$$

[enigma1234]

Solución:

Spoiler: mostrar

Sea la función generadora $F(x)=a_1x+a_2x^2+a_3x^3+....$, de la definición es fácil notar que $2a_n=\sum \limits _{i=1}^{n-1}a_ia_{n-i}$, veamos que:
$$F(x)^2=\sum \limits _{n=2}^{\infty}(\sum \limits _{i=1}^{n-1}a_ia_{n-i}\times x^n)=\sum \limits _{n=1}^{\infty}(2a_n\times x^n)=2\sum \limits _{n=2}^{\infty}(a_n\times x^n)=2(F(x)-a_1x)$$
$$\to F(x)^2=2F(x)-x\to (F(x)-1)^2=1-x$$
$$F(x)=1+\sqrt{1-x}\text{ o } F(x)=1-\sqrt{1-x}$$
Ahora para que esto tenga sentido como función generatriz necesitamos que $-1\leq x\leq 1$ y como $F(0)=0$ tenemos que:
$$F(x)=1-\sqrt{1-x}\text{ $\forall$ $-1\leq x\leq 1$}\to F(1)=\sum \limits_{n=1}^{\infty} a_n=1$$

[Fran5]

Que bolu... me olvidé que había un $2a_1$ en la recurrencia
Con razón me daba $2$.