La recurrencia de la relación no funciona como se espera

Question

Yo estaba tratando con la siguiente fórmula recursiva que tenía tres constantes ($k_1, k_2, k_3$) donde $x$ siempre será un número entero:

$$ f(x) = \begin{cases} 0 & if x = 1\\ k_1f(x-1) + k_2x + k_3 & if x \ge 2\\ \end{casos} $$

Yo quería encontrar una identidad para este tipo específico de forma recursiva definida por la función que puede ser expresada en términos de $x$.

La primera cosa que hice fue para operar la función para el propósito de dividir el problema en partes más pequeñas y, por ello, reducir el problema a una función. Y así lo hice:

$$ f(1) = 0\\ f(2) = 2k_2 + k_3\\ f(3) = k_1(2k_2 + k_3) + 3k_2 + k_3\\ f(4) = k_1^2(2k_2 + k_3)+ k_1(3k_2 + k_3) + 4k_2 + k_3\\ f(5) = k_1^3(2k_2 + k_3)+ k_1^2(3k_2 + k_3) + k_1(4k_2 + k_3) + 5k_2 + k_3\\ \vdots\\ f(x) = \sum_{i=1}^{x-1}k_1^{i-1}(ik_2 + k_3) $$

En ese momento, yo quería encontrar una manera de reemplazar la suma de un algebratic expresión con el mismo resultado. Para ello, he asumido este identidades eran verdaderas.

Mi primer paso fue modificar la fórmula para ser capaz de aplicar las identidades. A continuación se muestra, la mayoría de los procesos y la simplificación.

$$ f(x) = \sum_{i=1}^{x-1}ik_2k_1^{i-1} + k_3k_1^{i-1}\\ f(x) = \sum_{i=1}^{x-1}ik_2k_1^{i-1} + \sum_{i=1}^{x-1}k_3k_1^{i-1}\\ f(x) = k_2(\sum_{i=1}^{x-1}ik_1^{i-1}) + k_3(\sum_{i=1}^{x-1}k_1^{i-1})\\ f(x) = k_2(\frac{\sum_{i=1}^{x-1}ik_1^i}{k_1}) + k_3(\frac{\sum_{i=1}^{x-1}k_1^i}{k_1})\\ f(x) = \frac{k_2}{k_1}(\frac{k_1 - xk_1^x + (x - 1)k_1^{x+1}}{(1 - k_1)^2}) + \frac{k_3}{k_1}(\frac{k_1 - k_1^x}{1 - k_1})\\ \vdots\\ f(x) = \frac{(k_1-1)k_1^xk_2x+((k_1-1)k_1^x-k_1^2+k_1)k_3+(k_1^{x+1}+k_1)k_2)}{(k_1^3-2k_1^2+k_1)}\\ $$

El problema viene cuando me calcular el resultado. Mi primer problema es que, al $k_1 = 0$ o $k_1 = 1$, lo que significa que el denominador es igual a 0, ya que la fórmula es inútil en este caso. Eso significa que, ya que no cumplió con las expectativas iniciales, que eran capaces de calcular cualquier combinación de $k_1$,$k_2$ y $k_3$$\in \Bbb Z$, la función está mal.

Aparte de eso, cuando me calcular el resultado con cualquier otra combinación de las constantes, el resultado no es el mismo que el recurrente función de resultados.

Este es un ejemplo en el que $k_1 = 2$, $k_2 = 2$ y $k_3 = 2$:

----------------------------------
| x | Recursivo | No-recursivo |
----------------------------------
| 1 | 0 | 8 |
| 2 | 6 | 20 |
| 3 | 20 | 48 |
| 4 | 50 | 112 |
| 5 | 112 | 256 |
| 6 | 238 | 576 |
| 7 | 492 | 1280 |
| 8 | 1002 | 2816 |
| 9 | 2024 | 6144 |
| 10 | 4070 | 13312 |
| 11 | 8164 | 28672 |
| 12 | 16354 | 61440 |
| 13 | 32736 | 131072 |
| 14 | 65502 | 278528 |
| 15 | 131036 | 589824 |
----------------------------------

En resumen, lo que quiero saber es si me he equivocado en algunas de las operaciones y si hay una alternativa para llegar a la fórmula que estoy buscando.

Gracias por su interés! Yo wold agradezco cualquier aporte.

Answer 1

Esta es una costumbre que no homogénea de la ecuación recurrente.

Primero vamos a resolver la ecuación homogénea $$f(x) = k_1f(x-1).$$ Its general solution is $f_0(x) = Ck_1^x$. Next we find a particular solution of the non-homogeneous equation in the form $f_1(x)=ax+b$: $$ ax+b = k_1[a(x-1)+b] + k_2x + k_3. $$ Llegamos $a$ $b$ a partir de ecuaciones $a=k_1a+k_2, \ \ b=-k_1a+k_1b+k_3$. La solución general de la no homogénea de la ecuación es $f_0+f_1$. La constante $C$ se encuentran a partir de la condición inicial $f(1)=0$.

Answer 2

Como se señaló en los comentarios, la fórmula es $f(n) = \sum_{i=0}^{n-2}k_1^i((n-i)k_2+k_3)$.

Esto resuelve a

$\displaystyle\frac{k_1^n(2k_2+k_3)-k_1^{n-1}(k_2+k_3)-k_1(k_2(n+1)+k_3)+k_2n+k_3}{(k_1-1)^2}$

Así, por ejemplo, si $n= 10$$k_1 = k_2 = k_3 = 2$, tenemos

$2^{10}(2(2)+2) - 2^{9}(2+2)-2(2(11)+2)+2(10)+2 = 2^{10}(6)-2^{9}(4)-48+22$

$ = 6144-2048 -26 = 4070$

Answer 3

Dado $f(1)=0$$f(n)=k_1f(n-1)+k_2n+k_3$$n\in{\Bbb N}^{\ge2}$, se puede notar una suma formulario para $f(n)$: Si me temporalmente definir $g(n)=k_1^{-n}f(n)$, obtenemos la recurrencia $$k_1^ng(n)=k_1^ng(n-1)+k_2n+k_3\implies g(n)=g(n-1)+k_1^{-n}(k_2n+k_3),$$

por lo $g(n)=\sum_{i=2}^n k_1^{-i}(k_2i+k_3)$ $f(n)=\sum_{i=2}^n k_1^{n-i}(k_2i+k_3)$ (donde el índice empieza en $2$ debido a que el primer término distinto de cero se produce por $f(2)$).

Para hacer la suma anterior no recursivo, comprobamos nuestras tablas para ver

$$\begin{align} \sum_{i=0}^{n-1} a^i&=\frac{1-a^n}{1-a} \\ \sum_{i=0}^{n-1}ia^i&=\frac{a-na^n+(n-1)a^{n+1}}{(1-a)^2}, \end{align}$$

así $$\begin{align}f(n)&=\sum_{i=2}^n k_1^{n-i}(k_2i+k_3) \\ &=\sum_{i=0}^{n-2} k_1^i(k_2(n-i)+k_3) \\ &=(k_2n+k_3)\sum_{i=0}^{n-2} k_1^i-k_2\sum_{i=0}^{n-2}ik_1^i \\ &=(k_2n+k_3)\frac{1-k_1^{n-1}}{1-k_1}-k_2\frac{k_1-(n-1)k_1^{n-1}+(n-2)k_1^n}{(1-k_1)^2} \\ &=\frac{-k_1^{n-1} (k_2+k_3)+k_1^n (2 k_2+k_3)-k_1 (k_2 n+k_2+k_3)+k_2 n+k_3}{(k_1-1)^2}, \end{align}$$

donde la última expresión es el resultado de Mathematica en el original de la recurrencia.

---

Alternativamente, el conocer la forma de la respuesta, podemos, de hecho, acaba de "adivina la solución": el $n$ dependencia de la respuesta es $f(n)=A\alpha^n+Bn+C$, y hay buenas razones para adivinar esto mirando el original de la ecuación de recurrencia. Suponiendo que esta ecuación es correcta, se puede conectar a la repetición:

$$f(1)=0=A\alpha+B+C$$ $$\begin{align}f(n)=A\alpha^n+Bn+C&=k_1(A\alpha^{n-1}+B(n-1)+C)+k_2n+k_3 \\ &=\frac{k_1A}\alpha\alpha^n+(k_1B+k_2)n+k_1(C-B)+k_3 \end{align}$$

Comparando estas ecuaciones término por término, vemos que $A=-\frac1\alpha(B+C)$, $k_1=\alpha$, $k_1B+k_2=B$, y $C=k_1(C-B)+k_3$ (cuatro ecuaciones con cuatro incógnitas). Rewiting la solución en términos de sólo $B$$C$, obtenemos $f(x)=B(n-k_1^{n-1})+C(1-k_1^{n-1})$, y los otros dos a resolver para encontrar $$k_1B+k_2=B\implies B=\frac{k_2}{1-k_1}$$ and $$C=k_1\left(C-\frac{k_2}{1-k_1}\right)+k_3\implies C=\frac{k_3(1-k_1)-k_1k_2}{(1-k_1)^2},$$ así que nuestra respuesta final es

$$f(n)=(1-k_1^{n-1})\frac{k_3(1-k_1)-k_1k_2}{(1-k_1)^2}+(n-k_1^{n-1})\frac{k_2}{1-k_1},$$

que también está de acuerdo con la respuesta anterior.

---

Edit: Al $k_1=1$, la fórmula anterior no funciona, porque ya no hay un crecimiento exponencial; en lugar de la recursividad es $f(n)=f(n-1)+k_2n+k_3$, que es una suma de términos lineales y, por lo tanto cuadrática. Así que yo creo que esta vez es $f(n)=Dn^2+Bn+C$, por lo que el $f(1)=0=D+B+C$ y $$\begin{align} Dn^2+Bn+C=f(n-1)+k_2n+k_3&=D(n-1)^2+B(n-1)+C+k_2n+k_3 \\ &=Dn^2+(B-2D+k_2)n+(D-B+C+k_3), \\ \end{align}$$

de dónde $2D=k_2\implies D=\frac{k_2}2$$B=D-k_3=\frac{k_2}2-k_3$, y $D+B+C=0\implies $ $C=k_3-k_2$. Por lo tanto $$f(n)\Big|_{k_1=1}=\frac12(k_2n^2+(k_2-2k_3)n+2(k_3-k_2)).$$

Una forma alternativa de obtener esta respuesta es tomar el límite de la expresión anterior para$f(n)$$k_1\to1$, que es sin duda el camino más fácil. Así, aunque la expresión original se define para todos los $n,k_1,k_2,k_3\in{\Bbb R}$$k_1\ne1$, la singularidad en $k_1=1$ es "desmontable" y puede ser reparado con esta definición alternativa para $k_1=1$ a hacer una función que es continua en a $(n,k_1,k_2,k_3)\in{\Bbb R}^4$.