Recursion tree exercises

Exercise 1:

For the following recurrence relation and for a particular value of N > 1, we have expanded the recursion tree until we hit 1024 leaf nodes.

How many internal nodes will the tree have (including the root node).

Exercise 2:

A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same level. Level 0 of a tree is its root node. Level 1 of a perfect binary tree contains 2 nodes. How many nodes would Level 20 of a perfect binary tree contain?

Exercise 3:

Given the following recurrence relation:

$$\begin{equation}T(N) = \begin{cases} a, & \text{if N=1}.\\ b + T\left(\frac{N}{4}\right), & \text{N > 1}. \end{cases}\end{equation}$$

Determine its closed form.

Exercise 4:

$$\begin{equation} T(N) = \begin{cases} a, & \text{if N=1}.\\ b + 3T\left(\frac{N}{3}\right), & \text{N > 1}. \end{cases}\end{equation}$$

Determine the close form.