¿Cómo se desarrolla una relación de recurrencia para la función $f(n) = 5n^2 +3$ donde $n \in \mathbb{Z}^+$ ?

Question

En un examen mío, me pidieron encontrar una relación de recurrencia para la función $f(n) = 5n^2 +3$ donde $n \in \mathbb{Z}^+$ . Necesitaba proporcionar un caso base y la relación real en sí. Sé que el caso base es para $n = 1$ eran $f(1) = 8$ pero no tengo ni idea de cómo derivar la relación a partir de aquí.

La clave de respuesta del profesor es la siguiente, pero no entiendo de dónde viene la intuición/motivación para esta solución:

$f(1) = 8, f(n) = 5n^2 + 3 = 5(n - 1)^2 + 3 + 5(2n - 1) = f(n - 1) + 10n - 5$

¿Por dónde empiezo? Los pasos anteriores me parecen, al menos a mí, sacados arbitraria y mágicamente de la nada...

Answer 1

Estás intentando escribir una recurrencia de la forma $f(n)=f(n-1)+\text{ something.}$ Basta con sustituirlo para saber qué tiene que ser ese algo. Se le da que $f(n)=5n^2+3$ Así que $f(n-1)=5(n-1)^2+3.$ Entonces $f(n)-f(n-1)=5n^2+3-5(n-1)^2+3=10n-5$ y ya tienes tu algo.

Answer 2

Otra forma de resolverlo es por simple eliminación algebraica. Consideremos dos términos consecutivos:

$$ \begin{align} f(n) &= 5n^2+3 \\ f(n-1) &= 5(n-1)^2+3 = 5n^2-10n+8 \end{align} $$

Consideremos ahora $k = n^2$ como variable independiente:

$$ \begin{align} f(n) &= 5k+3 \\ f(n-1) &= 5k-10n+8 \end{align} $$

Elimine $k$ entre las dos ecuaciones, y se obtiene la recurrencia contabilizada:

$$f(n) = f(n - 1) + 10n - 5$$

Puedes ir un paso más allá. Escribe dos términos consecutivos de esta última recurrencia:

$$ \begin{align} f(n) &= f(n - 1) + 10n - 5 \\ f(n-1) &= f(n - 2) + 10(n-1) - 5 = f(n-2) +10 n -15 \end{align} $$

Ahora eliminar $n$ entre estas dos ecuaciones, y se obtiene una recurrencia lineal estándar para $f(n)\,$ :

$$ f(n)-f(n-1)=f(n-1)-f(n-2)+ 10 \;\;\iff\;\; f(n)=2 f(n-1)-f(n-2)+10 $$

Answer 3

La motivación de la reescritura $f(n)$ de esta manera, es adquirir una ecuación de la forma $$f(n)=g(f(n-1)),$$ es decir, tenemos que reescribir $f(n)$ de modo que obtengamos alguna función de $f(n-1)$ .
En este caso, esta función es $$g(x)=x+10n-5.$$

Ahora puedes deducir directamente la relación de recurrencia, enchufando $g$ en $x_{n+1}=g(x_n)$ .
Aquí, obtenemos el resultado $$x_1=8,~~x_{n+1}=x_n+10n-5$$