用數學歸納法證明電影院找零問題。

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)的節點值。