1

Basis Step: Test to see if this holds when $n = 1$ . If we have a maximal binary tree of $n = 1$ , we must have two children.
```
graph G {
	node[shape=point]
 1--2,3
}
```
Hence it has $2$ leaves, the statement says that it must have $2^{n} = 2^{1} = 2$ leaves which is true.

Inductive Step: Assume that the maximal full binary tree height $n$ has $2^{n}$ leaves. (IH) Now try to make a binary tree of height $n + 1$ , we take one new vertex and call it our root. Now we can take the maximal full binary tree of height $n$ from earlier, and let this be both the left and right child of our root.
```
graph G {
	node[shape=point]
 1--2,3
 
 subgraph cluster0 {
 	2--4,5
 }
 
 subgraph cluster1 {
 	3--6,7
 }
}
```
By the IH, we know that a maximal full binary tree of height $n$ has $2^{n}$ leaves, so our new tree with the two maximal trees of height $n$ has $2^{n} + 2^{n}$ leaves.
$2^{n} + 2^{n} = 2 \times 2^{n} = 2^{n + 1}$
This is the IH with $n + 1$ , hence by mathematical induction, for all positive integers $n$ , a maximal full binary tree of height $n$ has $2^{n}$ leaves.
```
title: Likely correct answer.
```
We know that a maximal full binary tree with height $n$ must have $2^{n}$ leaves. Let $l$ be the number of leaves.
$l ∴ l \geq 2^{n} \geq 2^{n - 1}$
```
title: Incomplete.
```

2

title: Correct answer.