Concept 7.6 (Basic Recursion). 1. A fractal tree is a simple recursive structure created iteratively as follows: Start with a single branch (leftmost picture). At each following step, we add two new branches on the end of each previous branch. The figure shows the first four steps. Step o has one "end-branch," Step 1 has two end-branches", Step 2 has four "end-branches" and so on. / N Y NY (a) Draw the fractal trees corresponding to Step 4 and Step 5 of the recursion. (b) Write an explicit definition for (an), where an = the number of end-branches at Step n. (C) Write a recursive definition for (an)=0- 2. Let (a,n)=, be the sequence where an = the number of bitstrings of length n that contain consecutive zeros. (a) Write down the values of a0, a1, a2, a3, and a4. (b) Find a recurrence relation for a5. Find a recurrence relation for an