MathLabs

Problem 3

Let mm and nn be arbitrary non-negative integers. Prove that (2m)!(2n)!m!n!(m+n)!\dfrac{(2m)!(2n)!}{m!n!(m+n)!} is an integer. (0!=10!=1).
Step 3 of 4: Derive the recurrence
Previous stepNext step
In plain words

Four times one neighbor minus the other collapses exactly to the target.

f(m,n)=4f(m,n−1)−f(m+1,n−1)f(m,n)=4f(m,n-1)-f(m+1,n-1)
Detailed analysis

Substituting the preceding identities, the coefficient of f(m,n)f(m,n) in 4f(m,n−1)−f(m+1,n−1)4f(m,n-1)-f(m+1,n-1) is 2(m+n)−(2m+1)2n−1=1\dfrac{2(m+n)-(2m+1)}{2n-1}=1. Hence the displayed recurrence holds.