[See Cascade of Recursive Calls. Denote by A_n the total number of function calls needed to calculate F_n. (These are called "Leonardo numbers".) It is easy to count initial values for A_n:

After staring at the binary trees of function calls one might guess that the numbers A_n can be defined by the recurrence:

It is not hard to see that this recurrence is correct. Picture the tree of recursive calls for F_n. The two children from the root are F_n-1 and F_n-2, and these each have A_n-1 and A_n-2 calls. Then add one more call for the root.

It might be hard to solve the recurrence, but if one guesses that

then the formula can be proved by induction:

Basis: It's easy to see the formula is true for n = 0, 1.

Induction step: We need what is called complete induction. So for some integer n, assume that

  A_i = 2 * F_i+1 -1, for each i <= n.

In particular, assume that A_n = 2 * F_n+1 -1 and A_n-1 = 2 * F_n -1

To Prove: A_n+1 = 2 * F_n+2 -1

Now A_n+1 = A_n + A_n-1 + 1 (the earlier formula)
  = (2 * F_n+1 -1) + (2 * F_n -1) + 1 (by the induction hypothesis)
  = 2*(F_n+1 + F_n) -1 -1 + 1 (simplifying)
  = 2*F_n+2 + 1. (definition of Fibonacci number)

Thus A_n+1 = 2 * F_n+2 -1, which is what we wanted to prove.

From the above page, you can see that it took about 70000 sec. to calculate F[60] using recursion. Suppose you have a machine 100 times as fast as the one used for the above calculation. Looking at the data, give a very rough estimate of the biggest Fibonacci number you could calculate in the same time on this faster machine, using the same recursive algorithm. Suppose instead your machine was a million times as fast. Again very roughly give the biggest Fibonacci number you could then calculate. [From the data you can see that increasing n by 5 takes roughly 10 times as long (a little more than that). So a machine 100 times as fast would be able to calculate F(70) in about the same time as this machine calculated F(60). Similarly, a machine a million times as fast would be able to calculate F(90) in about the same time as this machine calculated F(60).]

+---+---+------------+-------------+--------------+
| 1 | 2 |  column 3  |   column 4  |    column 5  |
+---+---+------------+-------------+--------------+
| a | b | a1=a xor b | b1=a1 xor b | a2=a1 xor b1 |
+---+---+------------+-------------+--------------+
| 0 | 0 |     0      |      0      |      0       |
| 0 | 1 |     1      |      0      |      1       |
| 1 | 0 |     1      |      1      |      0       |
| 1 | 1 |     0      |      1      |      1       |
+---+---+------------+-------------+--------------+

[Notice that b1 is the final value that b will have after executing the 3 statements, and a1 is the similar final value of a. For each of the four possible cases for values of a and b, we see that the a and b values have been interchanged after executing the 3 statements. This applies to single bits, but also bit-by-bit to 32-bit integers.]

1. Suppose you have the following information as bits: 01 11 10 11 00 10. Show the result of burning this to storage in the manner of the topic. Then burn the following information as a second generation and show the result: 10 01 00 11 10 10.

   [In each case below the red bits are burned. In rows 4 and 6 the 2nd generation information was the same as the 1st, so the 1st gen bits are left the same.]

   1st Info	1st Burn	2nd Info	2nd Burn
   01	001	10	101
   11	100	01	110
   10	010	00	111
   11	100	11	100
   00	000	10	101
   10	010	10	010

   [In each case below the red bits are burned. In rows 4 and 6 the 2nd generation information was the same as the 1st, so the 1st gen bits are left the same.]

2. Show that the formula involving xor lets you recover the original first two information bits correctly, both first and second generations (01 and 10). (See the xor page.) [For burned bits < a , b , c >, we can use the formula:
   < a ⊕ b , a ⊕ c >,  where ⊕ is exclusive-or to recover the original information. In the case of burned bits <0,0,1> above, the formula gives <0⊕0, 0⊕1> = <0,1> for the info bits. In the case of <1,0,1> above, the formula gives <1⊕0, 1⊕1> = <1,0>.]

1. The "difficulty" in the original program was that the numbers came out in the opposite order from what we wanted. The page shows two ways around this: pushing the numbers on a stack and then popping the stack, or using recursion (with an implicit stack in the background). In either Java or C describe briefly (without a full program) at least one other simple way around this problem. [It's easy to concatenate in the opposite direction or to stash digits in an array.]

2. Adapt one of the programs given so that you can convert the base 10 integer "123456789" to base 8. Change it again slightly so that you can convert this integer to base 16 (hexadecimal). You don't need to write a general program, but you will have to produce the hex digits somehow. [To get the hex digits, you can use a string alf="0123456789abcdef"; Then in C, if you want to print digit i (an int variable), instead print alf[i]. In Java print alf.charAt(i).]

1. log₃(x) = 6. [The equation mean the same as 3⁶ = x, or x = 729.]

2. 2*log₉(√x) - log₉(6x-1) = 0. [Rewritten:
   log₉( (√x)²/(6x - 1) ) = 0 , or x/(6x-1) = 1, or x = 1/5.
   (The base 9 had no effect on the solution.)

   Each expression above is equal to log₉(0.2) = log_e(0.2)/log_e(9) = -0.73248676.]

3. log x + log(x - 1) = log(3x + 12). [Simplying, we get the quadratic equation x² - 4x -12 = 0, with roots x = 6, and x = -2. The second root is extraneous, since we can't take the log of a negative number.]

4. ln(10) - ln(7-x) = ln(x). [Simplying, we get the quadratic equation x² - 7x +10 = 0, with roots x = 5, and x = 2. Each root is a solution.]

One of my favorite numbers is log₁₀(2) = 0.3010299956639812 (because of the three 9's).]