Recursive proof by induction with pseudocode

Question

I have the following pseudocode:

Function bar(n)
    Print '*';
    if n == 0 then
        Return;
    end
    for i = 0 to n − 1 do
        bar(i);
    end

The pseudocode prints stars. When $n = 0$, it prints 1 star. When $n = 1$, it prints 2 stars, $n = 2$ prints 4 stars’, $n = 3$ prints 8 stars… it appears this pseudocode follows a $2^n$ pattern.

The homework question asks: Let $T(n)$ be the number of times the above function prints a star (*) when called with input $n ≥ 0$. What is $T(n)$ exactly, in terms of only $n$?

From what I gather I just need to prove that the function is $2^n$.

Base case: $n = 0$, this produces 1 star. This is easily verifiable as the code stops running after the $n == 0$ comparison, and 1 star is printed before it ends.

Problem is I absolutely suck at proof by induction, and what always trips me up is how to expand upon the base case... especially in a situation with recursion. I could never figure out where to go next.

How do I prove how many times the function prints a star based on the based case? Furthermore, I hate having to resort to stackexchange for how to do proofs by induction. Is there some sort of technique or trick to solving/doing proofs that I'm way overlooking? Thank you.

Answer 1

Since $bar(n)$ calls all of $bar(0)$ through $bar(n-1)$, you'll need strong induction.

OK, aside from checking the claim for $n=0$, let $k$ be some number greater than $0$, and use the inductive assumption that for all $n<k$ we have that $bar(n)$ prints out $2^n$ stars.

Well, then $bar(k)$ prints out

$$1+\sum_{n=0}^{k-1} {2^n} = 1+(2^k-1)=2^k$$

stars.