Mathematical Induction Problem from Concrete Abstractions This is a problem from 'Concrete Abstractions' which is available free on the web[1]. It's a book similar to SICP. The problem:


  Exercise 2.16
     Consider the following procedure foo:


(define foo
  (lambda (x n)
    (if (= n 0)
        1
        (+ (expt x n) (foo x (- n 1))))))



  Use induction to prove that (foo x n) terminates with the value
          $$\frac{x^{n + 1} - 1 } {x - 1}$$
  
  for all values of x != 1 and for all integers n >= 0. You may assume that expt works
     correctly, (i.e., (expt b m) returns $b^m$). Hint: The inductive step will involve some algebra.


I've watched a video on induction on Khan Academy and read the induction material in the book, but I can't connect the dots to solve this problem.

Edit:
I am stuck at the Inductive step. My work:
Base Case:

(foo x 0)
(if (= n 0)
    1)


returns $1$ and

$\frac{x^{0+1} - 1} {x - 1} = \frac{x - 1}{x - 1} = 1$

So for the inductive hypothesis: Assume (foo x k) terminates in $\frac{x^{k+1} - 1}{x - 1}$ for all $k \geq 0$. Then for $k+1$:
I essentially add $k+1$ for the assumed formula above, so:
$\frac{x^{k+1} - 1}{x - 1} + k+1$. What I get is a long equation that I have no idea what to do with.
Your induction step is recorded incorrectly.

You wrote:

$$\frac{x^{k+1} - 1}{x - 1} + k+1$$

You should have written:

$$\frac{x^{k+1} - 1}{x - 1} + x^{k+1}$$

Basically, you are proving the formula for the sum of the geometric sequence.