Prove using MATHEMATICAL INDUCTION Prove If T is a full bina

Prove using MATHEMATICAL INDUCTION

Prove: If T is a full binary tree with n internal vertices, then T has 2n+1 total vertices.

Base Case: let n=0 2(0)+1=2
let n=1 2(1)+1=3

Induction: Assume true for n=k, 2k+1 for some k E Z+ (I think all my Induction part may be wrong)

Show true for n=k+1, 2(k+1)+1
2k+3

Thus, S(n) is true for all n E Z+

Induction part is where I get totally lost.

Solution

I think the proof which you wrote is write.