# structural induction

prove by structural induction that in any tree T, the number of leaves is 1 more than the number of nodes that have right siblings.

My proof so far:

s(n). in any tree T, the number of leaves(L) is 1 more than the number of nodes(N) that have right siblings.

s(1) for a tree of one node, there are no right siblings so n=1. The root itself is a leave so L =1. Thus L=n+1 is true, so the basis is true.

s(n+1)...Im stuck at the induction part here.

-
If this is homework, I think you're supposed to mark it as such. As a preliminary hint, structural induction is not mathematical induction. The second paragraph of that article might help you. – Paul VanKoughnett Oct 12 '10 at 0:17