Résoudre la récurrence inhabituelle avec deux variables
-
29-09-2020 - |
Question
J'ai la relation récurrence suivante:
$$ t (n, k)= t (n-1, k) + t (n-1, k + 1) $$
Avec les cas de base suivants (pour une certaine constante $ C $ ):
pour tous $ x \ leq c $ et pour tout $ k $ : $ t (x, k)= 1 $
pour tous $ y \ geq c $ et pour tout $ n $ : $ t (n, y)= 1 $
Je veux obtenir une formule pour $ t (n, 0) $ . Je pense que cela peut être vu qu'après $ i $ itérations Nous obtenons la relation suivante:
$ t (n, 0)=sum_ {j= 0} ^ i {n \ choisir {j}} \ cdot t (ni, j) $
Mais je ne sais pas si cela aide et ne peut pas continuer beaucoup plus loin que cela.
Ma question est $ - $ quelles techniques appropriées pour traiter de la récurrence avec 2 variables, et en particulier avec cette récurrence (où la deuxième variable augmente) ?
La solution
dans les cas $ c \ leq0 $ et $ c \ geq n $ vous avez $ T (n, 0)= 1 $ .
suppose que 0 $
Appliquer-le pour $ K= N-C $ .
nous obtenons $$ t (n, 0)=somm_ {i= 0} ^ {nc} \ binom {nc} {i} t (c, i)=sum_ {i= 0} ^ {nc} \ binom {nc} {i}= 2 ^ {nc} $$
si $ N> 2c $ La formule que nous obtenons est
$$ t (n, 0)=sum_ {i= 0} ^ {\ couleur {rouge} {c}} \ binom {\ couleur {rouge} {k }} {i} t (n- \ couleur {rouge} {k}, i) $$
mettre $ k= n-c $ nous obtenons
$$ t (n, 0)=sum_ {i= 0} ^ {c} \ binom {nc} {i} t (c, i)=sum_ {i= 0} ^ {c} \ binom {nc} {i} \ in o (n ^ c) $$
puisqu'il s'agit d'un polynôme de degré $ C $ .
Nous n'avons pas besoin de cela cette fois-ci, mais une technique qui pourrait être utile pour travailler avec des récurrences est Fonctions génératrices .
Autres conseils
Vous savez t (n, c) pour tous n.J'essaierais de déterminer T (N, C-1) pour tous N, puis T (n, C-2) et ainsi de suite.