Proof that a binary tree of height $h ≥ 1$ has at most $2^h$ vertices of degree 1 using induction

605 Views Asked by At

I need to prove by using principles of mathematic induction that a binary tree of height $h ≥ 1$ has at most $2^h$ vertices of degree $1$.

I am thinking that my base case should be: if $h = 1$,

$2^h = 2^1 = 2$

$2 ≥ 1$ therefore $p(h)$ is true

But then what should I do with the statement "vertices of degree 1"?

I tried to use (h+1) method; however, I don't think it is enough explanation. Is there any hint for it on how I can go about doing this?