secuencia $U_k=a_0U_{k-1}+a_1U_{k-2}+\cdots+a_{k-1}U_0$

Question

¿Existe una fórmula general para $U_k$ definido por

$$U_k=a_0U_{k-1}+a_1U_{k-2}+\cdots+a_{k-1}U_0$$

donde el $a_i$ están en progresión aritmética y $U_0=1$ ? ¿Existen siempre $c,d$ tal que $U_k\to cd^k$ como $k\to\infty$ ?

Si $a_n=n+1$ ,

$U_k=F_{2k}$ donde $F_n$ es el $n^{th}$ Número de Fibonacci.

Si $a_n=bn-1 \ \land \ b>1$ ,

$U_k=b^2(b+1)^{k-2} \ \forall \ k\geq2$

Answer 1

Muy algunas cosas de las funciones de generación...

Considere la serie $A(x)=\sum\limits_{k=0}^{+\infty}a_kx^k$ y $U(x)=\sum\limits_{k=0}^{+\infty}U_kx^k$ y asumir que $a_k=bk+2c$ para algunos fijos $b$ y $c$ . La fórmula de recursión para $(U_k)_{k\geqslant0}$ rinde $$U(x)=1+x\sum\limits_{k=1}^{+\infty}\sum\limits_{i=0}^{k-1}a_iU_{k-1-i}x^{k-1}=1+xA(x)U(x),$$ por lo que $U(x)=\frac1{1-xA(x)}$ . Por otro lado, $$A(x)=bx\sum\limits_{k=0}^{+\infty}kx^{k-1}+2c\sum\limits_{k=0}^{+\infty}x^k=\frac{bx}{(1-x)^2}+\frac{2c}{1-x}.$$ Juntando estas dos expresiones, se obtiene $U(x)=(1-x)^2/V(x)$ con $V(x)=(1-vx)(1-wx)$ , donde $$v=1+c+\sqrt{c^2+b},\ w=1+c-\sqrt{c^2+b}.$$ Utilizando esto y la descomposición $$\frac1{V(x)}=\frac1{v-w}\left(\frac{v}{1-vx}-\frac{w}{1-wx}\right),$$ el comportamiento asintótico de $(U_k)_k$ se deduce, ya que $$U_k=\frac{(v^2-1)v^{k-1}-(w^2-1)w^{k-1}}{v-w}.$$ Si $1+c\gt0$ y $c^2+b\gt0$ , $U_k=uv^k(1+o(1))$ con $u=(v^2-1)/(v(v-w))$ . Los otros casos son similares, algunos de ellos implican raíces complejas de la cuadrática $V(x)$ .

Answer 2

Supongamos que

$$U_k=\sum_{l=0}^{k-1}\big(a(k-l)+b\big)U_l$$

Entonces

$$V(x)-1=\sum_{k=1}^\infty U_kx^k=\sum_{k=1}^\infty \left(\sum_{l=0}^{k-1}\big(a(k-l)+b\big)U_l\right)x^k$$

$$=\sum_{l=0}^\infty \left(\sum_{k>l}^\infty \big(a(k-l)+b\big)x^k\right)U_l=\sum_{l=0}^\infty\left(\sum_{\delta=1}^\infty (a\delta+b)x^\delta\right)x^lU_l=\left(\frac{ax}{(1-x)^2}+\frac{bx}{1-x}\right)V(x)$$

de donde

$$V(x)=\left(1-\frac{ax}{(1-x)^2}-\frac{bx}{1-x}\right)^{-1}=\frac{(1-x)^2}{1-(a+b+2)x+(b+1)x^2}.$$

Como función racional, sus coeficientes serán una combinación lineal de potencias de los ceros del denominador anterior. Suponiendo un caso no degenerado, una potencia dominará a la otra y tendremos efectivamente $U_k\sim c d^k$ para algunos $c,d$ , según se desee.

Answer 3

La ecuación de recurrencia se escribe como $$U_k = \sum_{m=0}^{k-1} a_{k-1-m} U_m \tag{1}$$ Formemos la función generadora $f(x) = \sum_{k=0}^\infty x^k U_k$ . Entonces, sumando la ec. 1, multiplicada en ambos lados por $x^k$ , de $k=1$ a $\infty$ : $$f(x) - 1 = x \cdot f(x) \cdot \sum_{k=0}^\infty a_k x^k = x f(x) g(x)$$ Desde $a_k = a_0 + (a_1-a_0) k$ , $g(x) = \sum_{k=0}^\infty a_k x^k = a_0 \frac{1-2x}{(1-x)^2} + a_1 \frac{x}{(1-x)^2}$ . Por lo tanto,

$$f(x) = \frac{1}{1-x g(x)} = \frac{(1-x)^2}{(1-x)^2 - a_0 x + x^2 (2a_0 - a_1)}$$

El caso de $a_n = n+1$ que corresponde a $a_0=1$ y $a_1 = 2$ recuperamos la función generadora de $F_{2k}$ : $$f(x) = \frac{(1-x)^2}{1-3 x + x^2} = 1 + x + 3 x^2 + 8 x^3 + \mathcal{o}(x^3)$$

El caso de $a_n = b n -1$ mapas a $a_0 =-1$ y $a_1 = b-1$ y la función generadora: $$f(x) = \frac{(1-x)^2}{1-x- b x^2}$$ La función generadora anterior no corresponde a $U_k = b^2 (b+1)^{k-2}$ para $k \geqslant 2$ .

In[44]:= u[0] = 1;

In[45]:= u[k_Integer?Positive] := 
 u[k] = Expand[Sum[a[k - 1 - m] u[m], {m, 0, k - 1}]]

In[49]:= (Sum[u[k] x^k, {k, 0, 12}] /. {a[m_] :> b m - 1}) - 
 Series[-((-1 + x)^2/(-1 + x + b x^2)), {x, 0, 12}]

Out[49]= SeriesData[x, 0, {}, 13, 13, 1]

El crecimiento asintótico de $U_k$ está determinada por los polos de $f(x)$ .