¿Cómo deducir una fórmula cerrada dada un recursivo equivalente uno?

Question

Sé cómo demostrar que un cerrado fórmula es equivalente a un recursiva uno con la inducción, pero, ¿qué acerca de las maneras de deducir la forma cerrada inicialmente?

Por ejemplo:

$$ f(n) = 2 f(n-1) + 1 $$

Sé cómo usar la inducción para demostrar que $\forall n \ge1$:

$$ f(n) = 2^n f(0) + 2^n - 1 $$

Y yo era capaz de llegar con esa fórmula, en primer lugar, simplemente mediante el examen de manera informal. Parece que no debería haber sido un sencillo, de manera formal para deducir la forma cerrada de la definición recursiva en el primer lugar, pero estoy de borrado.

Sé que no siempre es fácil (por ejemplo, de Fibonacci), pero parece que no debería estar aquí. Por ejemplo, ¿cómo podría yo ir sobre el procedimiento de deducir la forma cerrada para:

$$ f(n) = 2*f(n-1) + k $$

Gracias.

Answer 1

Aquí está una generación de la función de método que usualmente funciona (no es elegante en este caso, sin embargo).

En primer lugar, recuerde que la infinita progresión geométrica de la fórmula (vamos a utilizar varias veces):

$$|x|<1\implies 1+x+x^2+x^3+\cdots=\sum_{n=0}x^n=\frac{1}{1-x}$$

Deje $G(x)=\sum_{n=0}f(n)x^n$. El coeficiente de la $x^n$ plazo es $f(n)$.

Multiplicar ambos lados por $x^n$:

$$f(n)x^n=2f(n-1)x^n+kx^n$$

Ahora, esta ecuación tiene $\forall n\ge 1, n\in\mathbb N$, por lo que sumamos todas las ecuaciones que podemos crear dejando $n=1, n=2$, etc.

$$\begin{align} \sum_{n=1}f(n)x^n &=\sum_{n=1}2f(n-1)x^{n}+k\sum_{n=1}x^n \\ \iff G(x)-f(0) &=2xG(x)+k\left(\frac{1}{1-x}-1\right) \\ \iff G(x)&=\frac{k}{(1-x)(1-2x)}+\frac{f(0)-k}{1-2x} \end{align}$$

Deje $\left[ G(x) \right]_{x^n}$ el valor del coeficiente de la $x^n$ el término de potencia de la serie $G(x)$.

Tenga en cuenta que disponemos de los siguientes hechos (vamos a utilizar):

$$\begin{align}\left[ \frac{1}{1-ax} \right]_{x^n}&=a^n \\ \left[ \frac{1}{(1-ax)(1-bx)} \right]_{x^n}&=\sum_{j=0}^{n}a^{j}b^{n-j}\end{align}$$

Así tenemos:

$$\begin{align} \left[ G(x) \right]_{x^n}&=\left[ \frac{k}{(1-x)(1-2x)} \right]_{x^n}+\left[ \frac{f(0)}{1-2x} \right]_{x^n}-\left[ \frac{k}{1-2x} \right]_{x^n} \\\\ &=k\sum_{j=0}^{n}1^j2^{n-j}+f(0)\cdot 2^n-2^nk \\\\ &=k\cdot (1+2^1+2^2+2^3+\cdots+2^n)+f(0)\cdot 2^n-2^nk \\\\ &=k\cdot \frac{2^{n+1}-1}{2-1}+f(0)\cdot 2^n-2^nk \\\\ &=2^{n+1}k-k+f(0)\cdot 2^n-2^nk \\\\ &=2^n(2k-k)+f(0)\cdot 2^n-k \\\\ &=2^nk+f(0)\cdot 2^n-k \\\\ &=2^nf(0)+k(2^n-1) \end{align}$$

---

Voy a agregar algunas otras fórmulas que pueden ayudar en el futuro:

$$\begin{align}\left[ \frac{1}{(1-x)^k}\right]_{x^n}&=\binom{n+k-1}{n}=\left(\binom{k}{n}\right) \\ \left[(1+x)^k\right]_{x_n}&=\binom{k}{n}\end{align}$$

Aquí $\left(\binom{k}{n}\right)$ denota conjunto múltiple coeficiente.

---

Una pequeña nota: Para mostrar lo grande que este método es (y para darle un ejercicio para ver si usted entiende el método de algo de práctica), me puede decir que puede ser usado para encontrar el cerrado fórmula para el $n$'th término de la secuencia de Fibonacci. La forma útil de la es (donde $F_0=0$):

$$F_n = \frac{(1 + \sqrt{5})^n - (1 - \sqrt{5})^n}{2^n \sqrt{5}}, \forall n\in\mathbb N_0$$

Sin embargo, nuestro método, en primer produce esta otra forma:

$$F_n=\frac{\sum_{j=0}^{n-1}(1+\sqrt{5})^{j}(1-\sqrt{5})^{n-j-1}}{2^{n-1}}, \forall n\in\mathbb N_0$$

Mediante manipulaciones algebraicas, usted puede cambiar de uno a otro. El ex fórmula es más útil porque nos ayuda a ver la fórmula más corta que podemos tener:

$$F_n = \lfloor \frac{(1 + \sqrt{5})^n}{2^n \sqrt{5}} + \frac{1}{2} \rfloor=\lfloor \frac{\phi^n}{\sqrt{5}}+\frac{1}{2} \rfloor, \forall n\in\mathbb N_0$$

Esta pregunta es acerca de aprender a resolver relaciones de recurrencia en general, por lo que este puede ser útil.

Answer 2

Podemos escribir $f(n)=2f(n-1)+k$ %#% $ de #% donde $$f(n)+k=2(f(n-1)+k)\iff g(n)=2g(n-1)$ es una progresión geométrica.

Ya que $g(n)=f(n)+k$, tenemos %#% $ #%

Answer 3

$$f(n) = 2f(n-1) + k \\ f(n-1) = 2f(n-2) + k \\ f(n-2) = 2f(n-3) + k \\ \dots \\ f(1) = 2f(0) + k$$ $$$$ $$\Rightarrow f(n) = 2f(n-1) + k= \\ 2(2f(n-2) + k)+k= \\ 2^2f(n-2)+(2+1)k=2^2(2f(n-3) + k)+(2+1)k= \\ 2^3f(n-3)+(2^2+2+1)k= \\ \dots \overset{*}{=} \\ 2^nf(0)+(2^{n-1}+2^{n-2}+\dots +2+1)k$$

Por lo tanto, $$f(n)=2^nf(0)+k\sum_{i=0}^{n-1}2^i= \\ 2^nf(0)+k\frac{2^n-1}{2-1}= 2^nf(0)+(2^n-1)k$ $

EDITAR:

$(*):$ Vemos que el $2^3f(n-3)+(2^2+2+1)k$ es de la forma $2^jf(n-j)+(2^{j-1}+2^{j-2}+\dots+2^2+2+1)k$

Después de algunos pasos tenemos los siguientes:

$2^nf(n-n)+(2^{n-1}+2^{n-2}+\dots+2^2+2+1)k= \\ 2^nf(0)+(2^{n-1}+2^{n-2}+\dots+2^2+2+1)k$

Answer 4

Cuando veo algo así, considero multiplicando ambos lados por $2^{-n}$: $$ \overbrace{2^{-n}f(n)}^{g(n)}=\overbrace{2^{1-n}f(n-1)}^{g(n-1)} + 2 ^ {-n} k $$ entonces, desde $g(n)=g(n-1)+a_n\implies g(n)=g(0)+\sum\limits_{j=1}^na_j\,$, tenemos $$\begin{align} \overbrace{2^{-n}f(n)}^{g(n)} &=\overbrace{f(0)}^{g(0)}+\sum_{j=1}^n2^{-j}k\\ &=f(0)+\left(1-2^{-n}\right)k \end {Alinee el} $$ así, multiplicando ambos lados por $2^n$ rendimientos $$ f (n) = 2 ^ nf (0) + \left (2 ^ n-1\right) k $$

Answer 5

No estoy 100% seguro tengo lo que significa, pero para este tipo de problemas (constantes arbitrarias $s, t$) una ecuación de diferencia es un buen enfoque, ya que inmediatamente deshacerse de $t$: $$ a_k = s a_ {k-1} + t\\ a_ {k+1} s a_k = t $$ ahora definir $\Delta a_{k+1} = a_{k+1} - a_k$. Se obtiene

$$ \Delta a_ {k+1} = s \Delta a_k = s ^ 2 \Delta a_ {k-2} = \ldots s ^ suma de ahora {k-1} \Delta a_1 $$ $k$ a 'back diferencia', hacer algunos álgebra y obtienes tu resultado.