用数学归纳法证明电影院找零问题。

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)的节点值。