Lesson 3

We have already encountered this recurrence relation when considering the number of nodes in a complete binary tree of height \(n\), and we know that \(M(n)=2^{n}-1\). We have seen one way of deriving this solution: guessing and proving. Let us consider another method. If the recurrence relation had no additive constant (i.e., \(M(n)=2M(n-1)\)), it would be immediately clear that the solution is powers of two. It turns out that the constant can be eliminated as follows. Consider the function (or sequence) \(M'(n)=M(n)+1\). It satisfies the following recurrence relation: \[\begin{align*}M'(n)&=M(n)+1=\\&=(2M(n-1)+1)+1=\\&=2M(n-1)+2=\\&=2M'(n-1).\end{align*}\] From this (and the initial condition \(M'(1)=2\)), it is clear that \(M'(n)=2^{n}\), and we conclude that \(M(n)=M'(n)-1=2^{n}-1\).