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)
        (+ (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)

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.

  • $\begingroup$ Where do you get stuck? Are you able to work out by hand what this function does for $n=1$ and $x\neq 1$? $\endgroup$
    – Louis
    Commented Mar 13, 2014 at 20:10
  • $\begingroup$ 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. $\endgroup$
    – douglas
    Commented Mar 13, 2014 at 20:11

1 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.

  • $\begingroup$ That makes sense. I was confused by an example problem. Thank you! $\endgroup$
    – douglas
    Commented Mar 14, 2014 at 2:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.