Secuencia de números catalanes: ¿Por qué f (n) = 2 f (n-1) + 1?

El último patrón es una expresión recursiva, y necesita una condición de inicialización como

[matemáticas] f (1) = 1 [/ matemáticas]

para que sea equivalente a la primera definición, suponiendo que [math] f (n) [/ math] se define en [math] n \ in \ mathbb {N} [/ math].

Si existe una [matemática] una [/ matemática] que

[matemáticas] f (n) + a = 2 (f (n-1) + a), [/ matemáticas]

Tenemos

[matemáticas] f (n) = 2f (n-1) + a [/ matemáticas]

donde [matemáticas] a = 1 [/ matemáticas]. Como [matemáticas] f (1) + 1 = 2 ^ 1 = 2 [/ matemáticas], entonces

[matemáticas] f (n) + 1 = 2 ^ n, [/ matemáticas]

y, equivalentemente,

[matemáticas] f (n) = 2 ^ n – 1. [/ matemáticas]

Además, muchas secuencias se pueden escribir fácilmente en alguna forma recursiva. Por ejemplo,

  • [math] a_n = n! [/ math] se puede escribir como
    [matemáticas] a_n = \ begin {cases} 1, n = 0, \\ na_ {n-1}, n \ ge 1. \ end {cases} [/ math]
  • [matemáticas] b_n = \ dfrac {n (n + 1)} {2} [/ matemáticas] puede escribirse como [matemáticas] b_n = \ begin {cases} 1, n = 1, \\ a_ {n-1} + 1, n \ ge 2. \ end {cases} [/ math]
  • La secuencia de Fibonacci tiene una forma cercana
    [matemáticas] F_n = \ left (\ dfrac {1 + \ sqrt {5}} {2} \ right) ^ n + \ left (\ dfrac {1 – \ sqrt {5}} {2} \ right) ^ n , [/ math] pero su definición recusiva es más común, que es
    [matemáticas] F_n = \ begin {cases} 1, n \ in \ {1, 2 \} \\ F_ {n-1} + F_ {n-2}, n \ ge 3. \ end {cases} [/ matemáticas]

Related Content

¿Es esta ecuación de álgebra inherentemente solucionable o insoluble? Si es solucionable, ¿qué tipo de programa de computadora podría resolverlo por mí?

Si [matemáticas] \ cos \ frac {x} {2} \ cdot \ cos \ frac {x} {4} \ cdot \ cos \ frac {x} {8} \ cdots = \ frac {\ sin x} {x } [/ math], ¿cómo probamos [math] \ frac {1} {2 ^ 2} \ sec ^ 2 \ frac {x} {2} + \ frac {1} {2 ^ 4} \ sec ^ 2 \ frac {x} {4} + \ cdots = \ csc ^ 2 x- \ frac {1} {x ^ 2} [/ math]?

¿Podría decirme si cada problema cuya solución puede ser verificada por una computadora en tiempo polinómico puede ser resuelta por una computadora en tiempo polinómico?

¿Cuál es el comportamiento final de los polinomios? ¿Para qué necesitarías saber esto?

Si log (x + y) en la base 2 = log (x – y) en la base 3 = log 25 / log 0.2 en la base 10, encuentre los valores de x e y

More Interesting

Cómo integrar: [matemáticas] \ int \ frac {\ log x dx} {1 + x}

Para verificar si el número es raíz cuadrada o no sin usar la función sqrt?

¿Es sen ^ 2x + cos ^ 2x igual a -cos ^ 2x + sin ^ 2x?

¿Cuál es la aplicación del álgebra abstracta en física, excepto la teoría de grupos?

¿Qué es infinito más infinito?

[matemáticas] y = \ cos ^ {- 1} (2x + x ^ 2) [/ matemáticas]. Encuentra [math] dy / dx [/ math] – ¿En esta pregunta podemos usar la regla de la cadena?

Cómo integrar [math] \ int_0 ^ a (a \ csc \ theta) ^ 5 dx [/ math]

Matemática discreta: ¿Cómo demuestro si: [matemáticas] b ^ 2 – 4ac> 0 [/ matemáticas] y [matemáticas] a \ neq 0, [/ matemáticas] y luego [matemáticas] p (x) = ax ^ 2 + bx + c [/ math] tiene dos raíces reales distintas?

Matemáticas: ¿Qué significa [math] \ mathbb {R} ^ {n} = E ^ {(s)} \ oplus E ^ {(u)} \ oplus E ^ {(c)} [/ math] y [math] A: \ mathbb {R} ^ {n \ rightarrow} \ mathbb {R} ^ {n} [/ math] significa?

Si se da que: [matemáticas] \ sqrt {2} \ cos (A) = \ cos (B) + \ cos ^ 3 (B) [/ matemáticas] y [matemáticas] \ sqrt {2} \ sin (A ) = \ sin (B) – \ sin ^ 3 (B) [/ math], entonces ¿cuál es el valor de [math] \ sin (AB) = [/ math]?