\(i\) マス目に進む組み合わせの数を \(C(i)\) とすると,

\[C(i) = C(i-1)+C(i-2)\]

である.