0
$\begingroup$

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.

$\endgroup$
  • $\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 Mar 13 '14 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 Mar 13 '14 at 20:11
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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