Please do not answer using code and use induction.

Your manager proposed to generate IDs for customers based on what he calls Tribonaci numbers. They define Tribonaci numbers using the recurrence R(i)=R(i1)+R(i3), with the first three Tribonaci numbers defined as R(0)=1,R(1)=2,R(2)=2. They would like to assign the ith customer an ID of R(i). You tell them that they are crazy and that the IDs are going to be huge; in fact, you claim that the ith customer will have an ID number of at least 2i/2. Your manager, who has never taken lightly to criticism, threatens to fire you on the spot unless you can come up with a proof of your claim. (a) To save your job, use induction to prove that in fact R(i)2i/2 for all i2. (b) Your manager is perplexed. They didn't take CMPSC360 or CMPSC465 so they don't know what induction is and don't understand your proof. They propose a simple recursive algorithm to compute R(i). The algorithm simply makes the necessary recursive calls and then adds the results. You tell him that his algorithm will take exponential time, but your manager doesn't want to hear anything more about induction. They demand an intuitive picture instead of a proof. Luckily, you just covered something like this in class. Draw a recursion tree that shows the cascade of recursive invocations triggered by a single call to compute R(i). Three levels deep will suffice (i.e. your tree should have 4 levels)