用数学归纳法证明电影院找零问题。
n个人,每人只带50美分,m个人,每人只带了1美元纸币。n>=m。现要证明有
(n+m, n)-(n+m, n+1)
种排队的方法,使得那些仅带1美元纸币的人都能得到50美分的找零。
证明:
在直角坐标系中,找到两个格点(0,0), (n,m)。从(0,0)起始,每步距离是1,只能右行和上行,到(n,m)。如果右行代表带50美分的人,上行代表带1美元纸币的人。所有可行路径(<=(y=x))的个数就是能使电影院找零的排队方法是个数。把到某点的可行路径的个数看成此点的节点值。
那么,按归纳假定,格点(n-1,m)的节点值是
(n+m-1,n-1)-(n+m-1,n)
格点(n,m-1)的节点值是
(n+m-1,n)-(n+m-1,n+1)
显然,格点(n,m)的节点值就是上述两个节点值的和:
(n+m-1,n-1)-(n+m-1,n) + (n+m-1,n)-(n+m-1,n+1)
= (n+m, n)-(n+m, n+1) (1)
现在讨论归纳基础。(1,1),(2,1),...,(n,1)的节点值可以简单叠加验证。
因(2,1)的节点值=(2,2)的节点值,用(1)可以推出(3,2),(4,2),...,(n,2)的节点值。
以此类推,最后推出(m,m),(m+1,m),...,(n,m)的节点值。