Resolviendo la recurrencia inusual con dos variables.

Question

Tengo la siguiente relación de recurrencia:

$$ t (n, k)= t (n-1, k) + t (n-1, k + 1) $$

con los siguientes casos de base (para un recipiente de matemáticas constante $ C $ ):

para todos $ x \ leq c $ y para cualquier $ k $ : $ t (x, k)= 1 $

para todos $ y \ geq c $ y para cualquier $ n $ : $ t (n, y)= 1 $

Quiero obtener una fórmula para $ t (n, 0) $ . Creo que se puede ver que después de $ i $ iteraciones obtenemos la siguiente relación:

$ t (n, 0)=sum_ {j= 0} ^ i {n \ elegir {j}} \ CDOT T (NI, J) $

Pero no sé si ayuda y no puede continuar mucho más allá de eso.

Mi pregunta es $ - $ cuáles son las técnicas correctas para tratar la recurrencia con 2 variables, y en particular con esta recurrencia (donde aumenta la segunda variable) ?

Answer 1

En los casos $ C \ leq0 $ y $ c \ geq n $ tiene $ t (n, 0)= 1 $ .

Supongamos que $ 0 . Muestra esa $$ t (n, 0)=sum_ {i= 0} ^ {\ color {rojo} {k}} \ binom {\ color {red} {k}} { i} t (n- \ color {rojo} {k}, i) $$ para $ 0 \ leq k \ leq n-c $ y $ n \ leq 2c $ . Parece que esta es la fórmula que mencionó en la pregunta, excepto que el coeficiente binomial debe tener la misma cantidad que se está restando de la primera entrada de $ t $ .

Aplícalo para $ k= n-c $ .

Tenemos $$ t (n, 0)=sum_ {nc} \ binom {nc} {i} t (c, i)=sum_ {i= 0} ^ {nc} \ binom {nc} {i}= 2 ^ {}} $$

Si $ n> 2c $ La fórmula que obtenemos es

$$ t (n, 0)=sum_ {i= 0} ^ {\ color {roja} {c}} \ binom {\ color {rojo} {k }} {i} t (n- \ color {rojo} {k}, i) $$

Poner $ k= n-c $ obtenemos

$$ t (n, 0)=sum_ {c} \ binom {nc} {i} t (c, i)=sum_ {i= 0} ^ {c} \ binom {nc} {i} \ in o (n ^ c) $$

Dado que es un polinomio de grado $ C $ .

---

No lo necesitamos esta vez, pero una técnica que podría ser útil para trabajar con las recurrencias es Funciones generadoras .

Answer 2

usted sabe t (n, c) para todos n.Intentaría determinar T (N, C-1) para todos N, luego T (N, C-2) y así sucesivamente.