MQ65 --- Factorial

解題策略是模彷二項式係數C(n,r) = C(n - 1,r - 1) + C(n - 1,r) 般建立一個遞迴關係式

記f(m,n) = (2m)!(2n)!/[m!n!(m + n)!] f(m,n - 1)

= (2m)!(2n - 2)!/[m!(n - 1)!(m + n - 1)!]

= n(m + n)(2m)!(2n - 2)!/[m!n!(m + n)!]

f(m + 1,n - 1)

= (2m + 2)!(2n - 2)!/[(m + 1)!(n - 1)!(m + n)!]

= 2n(2m + 1)!(2n - 2)!/[m!n!(m + n)!]

現在4f(m,n - 1) - f(m + 1,n - 1)

= (2m)!(2n - 2)![4n(m + n) - 2n(2m + 1)]/[m!n!(m + n)!]

= (2m)!(2n - 2)!(4n^2 - 2n)/[m!n!(m + n)!]

= (2m)!(2n)!/[m!n!(m + n)!]

= f(m,n)

因此f(m,n) = 4f(m,n - 1) - f(m + 1,n - 1)...(1)

由此可以對n用數學歸納法証明所需結論

注意f(m,0) = (2m)!/(m!m!) = C(2m,m)是整數 (對所有的m)

假設當n <= k時f(m,k)是整數(對所有的m)

則當n = k + 1時﹐根據(1)式﹐f(m,k + 1)也是整數

根據數學歸納法﹐對所有的非負整數m,n﹐(2m)!(2n)!/[m!n!(m + n)!]是整數

4f(m,n - 1) - f(m + 1,n - 1) = f(m,n) 是怎想到的?