Funciones definidas recursivamente

Question

Estoy tomando una clase de verano de matemáticas discretas y me ha ido muy bien hasta ahora. Estoy nerviosa porque he revisado las diapositivas de la clase y los problemas de práctica, pero todavía no entiendo muy bien lo que hay que hacer. El ejemplo de problema que me dieron es:

Supongamos que $f$ se define por:

\begin {align} f(0) &= 0, \\ f(1) &= 1, \\ f(n + 2) &= f(n + 1) + 2 \times f(n) \end {align}

Pregunta: Encuentre $f(2), f(3), f(4), f(5), f(6)$

Ahora entiendo que lo que estoy haciendo es encontrar la función enchufando la función anterior, pero no entiendo el $f(n+2)$ . ¿Cómo interpreto esto? ¿Significa esto que para $f(2)$ Introduzco el resultado de $f(1)$ y añadir $2$ ¿a él? ¿O tengo que conectar $0$ desde $0+2 = 2$ y estoy tratando de encontrar $f(2)$ ?

Answer 1

No. Para $f(n+2)$ primero se calcula $n+2$ y, a continuación, aplique $f$ a ella.

Así, para $n=2$ queremos $f(n+2)=f(4)$ . Para calcular $f(2)$ tomamos $n=0$ en la ecuación para obtener $f(2)=f(1)+2 f(0)$ . Entonces para $f(3)$ tomamos $n=1$ en la ecuación para obtener $f(3) = f(2)+2f(1)$ .

Answer 2

Desde $f(n+2)=f(n+1)+2×f(n)$ , conectando $n=0$ produce $$f(2)=f(1)+2×f(0)=1+2×0=1$$

Y así con $n=1,2,3$ ... etc. :) Espero que esto ayude.

Answer 3

Esta función se define recursivamente como una función de las dos entradas anteriores. Así que para calcular $f(2)$ se necesitan los valores de $f(1)$ y $f(0)$ . Siguiendo la definición,

$f(2) = f(0 + 2) = f(1) + 2*f(0)$ .

Una forma equivalente de pensar en esta función recursiva es

$f(k) = f(k-1) + 2*f(k-2),\,\, k>1$