Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Mathematical Induction Problem from Concrete Abstractions

, ,
Problem Detail:

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.

#### Answered By : sds

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.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22596

3.2K people like this

#### Post a Comment

Let us know your responses and feedback