Proof by induction binary tree of height n has 2^(n+1)-1 nodes

Question

How would someone go about to prove by induction that a binary tree of height n has 2^(n+1)-1 nodes?

Answer 1

First of all, I have a BS in Mathematics, so this is a general description of how to do a proof by induction.

First, show that if n = 1 then there are m nodes, and if n = 2 then there are k nodes. From this determine the formula of m, k that works when n = 1 and 2 (i.e in your case 2^(n+1) - 1.

Next, assume that the same formula works for n as an arbitrary value. finally, show that the formula works for a height of (n+1). that is n implies n+1 (a single step increment). This last step is usually the most difficult, but you can use the results for n, 1 and 2 if necessary.

The idea is that you can see for n = 1 and 2 that the formula works when n is increased by 1. Then, if it is true for n, then by proving it is true for n+1, a diligent person could explicitly compute n = 1, 2 then 3, 4, etc. all the to n and then to n+1, in single step increments.