Timeline for How to solve this recurrence involving binomial coefficients?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 5, 2018 at 12:14 | vote | accept | hengxin | ||
| Apr 5, 2018 at 11:55 | comment | added | hengxin | I have obtained that $A(n,k) = c\binom{n}{k} - c$. Thanks. | |
| Apr 5, 2018 at 11:31 | comment | added | Yuval Filmus | Try again. My method works just as well in this case. | |
| Apr 5, 2018 at 11:28 | comment | added | hengxin | I just found that I have made a mistake: The initial conditions should be $A(n,0) = A(n,n) = 0$ instead of $A(n,0) = A(n,n) = 1$. $A(n)$ aims to count the number of additions in computing $\binom{n}{k}$ following the identity $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$. I failed to apply your method with such initial conditions. Therefore, I have removed the code and the backgroud, leaving only the recurrence to solve. However, can you solve this recurrence with the new initial conditions? (Maybe I should open a new post.) | |
| Apr 5, 2018 at 9:30 | comment | added | Yuval Filmus | Experience. Perhaps more interesting is to solve the recurrence when $A(n,0) \neq A(n,n)$. | |
| Apr 5, 2018 at 9:29 | comment | added | hengxin | Are there any clues for you to guess that $A(n,k) = \alpha \binom{n}{k} + \beta$? | |
| Apr 5, 2018 at 9:12 | history | answered | Yuval Filmus | CC BY-SA 3.0 |