MathLabs

第3問

任意の非負整数 mm と nn について、(2m)!(2n)!m!n!(m+n)!\dfrac{(2m)!(2n)!}{m!n!(m+n)!} が整数であることを証明せよ。(0!=10!=1)。
ステップ 3/4: 漸化式を導く
ざっくり言うと

一方の隣接値を4倍して他方を引くと目的の値になる。

f(m,n)=4f(m,n−1)−f(m+1,n−1)f(m,n)=4f(m,n-1)-f(m+1,n-1)
詳しい解説

前の2式を代入すると、4f(m,n−1)−f(m+1,n−1)4f(m,n-1)-f(m+1,n-1) における f(m,n)f(m,n) の係数は 2(m+n)−(2m+1)2n−1=1\dfrac{2(m+n)-(2m+1)}{2n-1}=1 となる。よって表示の漸化式を得る。