how could I make a general formula for this pattern?

Question

I am attempting to find a formula that describes the number of leaf nodes in a full binary tree of depth k, therefore nodes at a depth <k have exactly two children and the leaves are at depth K.

This gives me the following pattern.
A tree with 1 Node has 1 Leaf
A tree with 3 Nodes has 2 leaves
A tree with 7 Nodes has 4 leaves
A tree with 15 Nodes has 8 leaves
A tree with 31 Nodes has 16 leaves

I am trying to figure out a formula that tells the number of leaves given N = Number of Nodes but have not been able to figure it out

Answer 1

Hint: there exist $a$ and $b$ such that the number of leaves in a tree with $n$ nodes is $an+b$. Use two of the examples you've found already to find $a$ and $b$.

A tree with $n$ nodes has $\frac{n+1}{2}$ leaves. Equivalently, a tree with $2^k-1$ nodes has $2^{k-1}$ leaves.

Answer 2

Hint: Add one to the number of nodes and compare it to the number of leaves. Do you see a pattern?