how many nodes can a binary tree have at level n? Use induction to prove the answer

Question

This is a homework and i didn't have much time to spent on it but I know some of the answer and need a little help plz

i'm thinking like this assume we have:

1 node ----> Level 1

2,3 nodes ----> Level 2

3,4,5,6,7 nodes ----> level 3

4,5,6,.....,15 nodes ----> Level 4

5,6,7,8,9,.....,31 nodes ----> Level 5

node(s) interval from [ min=X node(s) TO max = 2^X - 1 node(s) ] where X represent the level

from now on i'm confused how to complete

Answer 1

As I recall to use induction you have to prove the Nth case and the N + 1th case. And we see for any N that the N + 1th level has exactly twice as many. Thus shown by 2^(N + 1) / 2^N = 2

The total number of nodes can be found by taking the sum from n = 0 to N - 1 of 2^n

You probably want a more conclusive and verbose answer, but thats the gist.