Mathematical Induction Problem from Concrete Abstractions

Question

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.

Answer 1

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.