Given the following recurrence relation
$$u(n,1) = 1$$ $$u(1,m) = 1$$ $$u(n,m) = u(n-1, m) + u(n, m-1)$$
with $n > 0, m > 0$,
how can one end up with a closed formula, without using generating functions?
Asked
Active
Viewed 67 times
0
-
I'm assuming that $n$ and $m$ are positive integers, and the given recurrence is for $n,m\geqslant 2$? – Math1000 Feb 01 '15 at 18:27
-
@Math1000 thanks, I added this conditions – stefan Feb 01 '15 at 18:28
-
Do you have a background about solving recurrence equations? – Mhenni Benghorbal Feb 01 '15 at 18:31
-
@Mhenni Benghorbal Well I know some of the ad hoc approaches like, guess & induct, or subtracting r(i) form r(i+1) and going down to r(1) this way... – stefan Feb 01 '15 at 18:35
-
Why no generating functions? – Did Feb 02 '15 at 17:05
-
@Did Because I was able to solve it using GF, but wanted to be able to solve it without too :) – stefan Feb 02 '15 at 20:45
-
"am I concluding correctly that there is no non-adhoc way of attacking such problems?" Incorrect, the non ad hoc way is to use generating functions. – Did Feb 02 '15 at 20:48
1 Answers
0
If you compute $u(n,m)$ for e.g. $1\leqslant n,m\leqslant 6$ you should see a pattern. In particular, look at the diagonals where $n+m=k$ for $k=1,2,\ldots$. I came up with
$$\displaystyle u(n,m) = \binom{n+m}n,$$
which clearly satisfies the recurrence, as
$$\displaystyle\binom{n+m}n = \binom{n+m-1}{n-1} + \binom{n+m-1}n.$$
Math1000
- 36,983
-
Thank you, so am I concluding correctly that there is no non-adhoc way of attacking such problems? – stefan Feb 01 '15 at 18:56
-
Well, that is generally my approach when I don't know a method to solve a problem off-hand. It just so happened that for this problem, that worked. The other way to go about it would be to recognize the recurrence as the binomial coefficients, but I am not great at combinatorics so I didn't see that immediately. – Math1000 Feb 01 '15 at 21:14