Ungewöhnliche Wiederholung mit zwei Variablen lösen

Question

Ich habe folgende Rezidivrelation:

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

mit den folgenden Basisfällen (für einige gegebene Konstante $ C $ ):

für alle $ x \ leq c $ und für jeden $ k $ : $ t (x, k)= 1 $

für alle $ y \ geq c $ und für jeden $ n $ : $ t (n, y)= 1 $

Ich möchte eine Formel für $ t (n, 0) $ erhalten. Ich denke, dass es zu sehen ist, dass nach $ i $ iterationen die folgende relation erhalten:

$ t (n, 0)=sum_ {j= 0} ^ i {n \ Wählen Sie {j}} \ cdot t (ni, j) $

Aber ich weiß nicht, ob es hilft und nicht viel weiter vorgehen kann.

meine Frage ist $ - $ Was sind die richtigen Techniken für den Umgang mit 2 Variablen und insbesondere mit diesem Wiederauftreten (wo die zweite Variable zunimmt)

Answer 1

in den Fällen $ c \ leq0 $ und $ c \ geq n $ Sie haben $ t (n, 0)= 1 $ .

Nehmen Sie an, dass $ 0 . Zeige, dass $$ T (n, 0)=sum_ {i= 0} ^ {\ color {rot} {k}} \ Binom {\ color {rot} {k}} { Ich} t (n- \ color {rot} {k}, i) $$ Für $ 0 \ LEQ K \ LEQ N-C $ und $ n \ leq 2c $ . Es sieht so aus, als ob dies die Formel ist, die Sie in der Frage erwähnt haben, mit der Ausnahme, dass der Binomialkoeffizient den gleichen Betrag haben sollte, der vom ersten Eintrag von $ T $ abgezogen wird .

Anwenden Sie es für $ k= N-C $ .

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

wenn $ n> 2c $ die Formel, die wir bekommen, ist

$$ t (n, 0)=sum_ {i= 0} ^ {\ color {rot} {c}} \ Binom {\ color {rot} {k }} {i} t (n- \ color {rot} {k}, i) $$

Setzen $ k= N-C $ Wir bekommen

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

Da es sich um ein Polynom von Grad $ C $ handelt.

---

Wir brauchten es diesmal nicht, sondern eine Technik, die nützlich sein könnte, um mit Wiederholungen zu arbeiten, ist Funktionen erstellen .

Answer 2

Sie kennen t (n, c) für alle n.Ich würde versuchen, t (n, c-1) für alle n, dann t (n, c-2) usw.) und so weiter.