Jump to content
  • Advertisement
Sign in to follow this  
bodchook

Concrete Abstractions Ex 2.16 (Proof by Induction)

This topic is 3495 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Howdy. I'm working my way through Concrete Abstractions, and I'm trying to understand this proof by induction thing. Here is the exercise (note, this is not homework, this is just self-study):
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
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 bm). Hint: The inductive step will involve some algebra.
The base case is n = 0, which is 1, which works. I think I understand the inductive hypothesis step, which is to assume that (foo x k) = ((x^k+1) - 1 / (x - 1)) for all values of k where x =/ 1 and 0 <= k < n. Not sure if that's right. As far as the inductive step.. I don't know how to do it. I kind of understand the example in the book where the author does an inductive proof of the square procedure, but in trying to apply that same process to this foo procedure isn't working for me. Any help would be appreciated! Edit: Another example, this one I think is easier, but I don't understand how it proves anything: Prove by induction that for every nonnegative integer n the following procedure computes 2n:
(define f
   (lambda (n)
      (if (= n 0)
          0
          (+ 2 (f (- n 1))))))

So, the Base case (n = 0) checks out, and if I assume that f(k) = 2k where 0 <= k < n, then f(n-1) = 2 + 2(n-1) = 2 + 2n - 2 = 2n. So, didn't I just prove that this function works by assuming that it does? Huh? [Edited by - bodchook on December 23, 2008 12:32:41 PM]

Share this post


Link to post
Share on other sites
Advertisement
It sounds like you know exactly what to do but it feels somehow unjustified to you. I'm betting if you do a google search on induction you can find some simpler examples.

What you're doing is showing the base case is true and that given an arbitrary case you can show the next case is true. But this means precisely that you can take the base case n=0 (for example) and show the case n=1 is true. And once you know n=1 is true, you know n=2 is true, and from there n=3 must be true, etc. Thus given any natural number n, you can show the formula is true by starting at the base case and working your way up. Since everyone agrees induction is valid, you can just state the base case and the induction step, wave the magic induction wand and then skip the rest of the argument.

It's also worth mentioning this whole process is very opaque. You're proving the formula is true, but you're not providing any insight into how the formula was generated. I always found that very unsatisfying.

Share this post


Link to post
Share on other sites
Quote:
Original post by jdindia
It sounds like you know exactly what to do but it feels somehow unjustified to you. I'm betting if you do a google search on induction you can find some simpler examples.

What you're doing is showing the base case is true and that given an arbitrary case you can show the next case is true. But this means precisely that you can take the base case n=0 (for example) and show the case n=1 is true. And once you know n=1 is true, you know n=2 is true, and from there n=3 must be true, etc. Thus given any natural number n, you can show the formula is true by starting at the base case and working your way up. Since everyone agrees induction is valid, you can just state the base case and the induction step, wave the magic induction wand and then skip the rest of the argument.

It's also worth mentioning this whole process is very opaque. You're proving the formula is true, but you're not providing any insight into how the formula was generated. I always found that very unsatisfying.

Yeah it sounds like you are getting hung up on the whole induction thing.
Just think of it as knocking over dominoes;)
If that doesn't make sense check out induction 1 and 2 on this page. Probably the best explanations I've ever seen on it. In class problem #1 solution should really make it clear as a lightbulb lighting up in your head;)
*and it really helps to see a case where induction fails as they show*

p.s. And you can't help but laugh how Bill Gates shows up in an induction proof-LOL!


[Edited by - daviangel on December 24, 2008 6:14:43 PM]

Share this post


Link to post
Share on other sites
Induction, basically, works that you prove that something works for n=1 and then in the induction step you prove that if it works for some n, it also works for n+1. When you've got these two steps, you've got it all -- if it works for n=1, it must work for n+1 = 2, right? Thanks to the induction step. And if it works for n=2, it also works for n+1 = 3. And so forth.

This is a simplified explanation -- you don't have to do induction over integers -- you can do induction over the number of vertices in a tree or the number of circles in a graph or various other weird stuff.

Anyway, I know thinking of it this way helped me understand induction. x)

Share this post


Link to post
Share on other sites
I really appreciate the replies! I went through the Induction I and II slides and in-class problems that daviangel linked to. The exact problem I originally posted was actually the first example in Induction I slides.. so that was very helpful! I can see that I need to brush up on my algebra a bit.. but that's no big deal. Thanks for the help =)

Share this post


Link to post
Share on other sites
I have always understood induction by understanding why it works (that is, how do you prove that proof by induction works?)

Suppose that you have a property P(i) over integers. Assume that P(0) is true, and that ∀n>0, P(n-1) => P(n).

Consider now the set of integers for which P() is false. If it isn't empty, then it has a smallest element 'n'. That smallest element cannot be 0 because P(0) is false, which means that 'n-1' is also an integer and, since 'n' was the smallest integer for which the property is false, P(n-1) is true and, because of the induction hypothesis, P(n) is true: it is therefore impossible for that set of integers to be non-empty.

The general rule can be stated as such:

  • If you have a set of elements with an order relationship on them.
  • Such that every non-empty subset of these elements has at least one minimal element.
  • And you have a property that states "For every element, if all elements smaller than this element have property P, then that element also has property P"
  • And all the minimal elements of that set also have that property P
  • Then all elements of the set have property P.


Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Consider now the set of integers for which P() is false. If it isn't empty, then it has a smallest element 'n'. That smallest element cannot be 0 because P(0) is false, which means that 'n-1' is also an integer and, since 'n' was the smallest integer for which the property is false, P(n-1) is true and, because of the induction hypothesis, P(n) is true: it is therefore impossible for that set of integers to be non-empty.

ToohrVyk I find that explanation to be confusing. Since we already assumed that P(0) is true why is it you say that P(0) is false? Your use of P and 0 is ambiguous, is P a proposition or a function? is 0 an index or number? Just because P(0) is false does not entail that 'n-1' is an integer. What is 'n-1'?

Your basic argument recalls to mind a proof of Finite Induction via the Well Ordering Principle. But that proof goes a bit differently.

Quote:
The general rule can be stated as such:

  • If you have a set of elements with an order relationship on them.
  • Such that every non-empty subset of these elements has at least one minimal element.
  • And you have a property that states "For every element, if all elements smaller than this element have property P, then that element also has property P"
  • And all the minimal elements of that set also have that property P
  • Then all elements of the set have property P.

Bullet Point One and Two are the same thing and are sufficient to prove Induction each on its own as the well ordering principle is equivalent to induction. Statements 3,4,5 reduce in my mind to a tautology: If all elements have property P then all elements have property P.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!