Mathematical Induction Problem from Concrete Abstractions

This is a problem from 'Concrete Abstractions' which is available free on the web. 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.

• Where do you get stuck? Are you able to work out by hand what this function does for $n=1$ and $x\neq 1$? – Louis Mar 13 '14 at 20:10
• Louis: Sorry, I should have mentioned this. I am fine with the base case n = 0. And I think I understand the inductive hypothesis. It's the Inductive Step. I will edit the original post explaining this / my work. – douglas Mar 13 '14 at 20:11

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.

• That makes sense. I was confused by an example problem. Thank you! – douglas Mar 14 '14 at 2:00