이런 유형의 점화식은 이 튜토리얼 맨 앞에서 언급한 교과서에 잘 나와 있지만 여기서는 귀납적인 방법을 이용해보자. 위의 점화식으로 첫 몇 항을 계산한 후 패턴을 찾아 그 패턴이 모든 양의 정수 n에 적용된다는 것을 증명하면 된다.
M(n)의 첫 몇 항을 살펴보면 M(n) = 2n - 1인 것 같다. 우선 n = 1일 때는 당연히 M(1) = 21 - 1 = 1이다. n > 1에 대해 이 식이 성립한다는 것을 증명하는 가장 쉬운 방법은 이 공식을 점화식에 대입한 후 1보다 큰 모든 정수에 대해 식이 성립한다는 것을 보여주는 것이다. 다음과 같이 해보면 실제로 식이 성립한다는 것을 알 수 있다.
M(n) = 2n - 1 그리고 2M(n - 1) + 1 = 2(2n-1 - 1) + 1 = 2n - 1