Recursive using strong induction and structural induction (rosen)

[DrWillVKN]

Homework Statement

Let S be subset of set of ordered pairs of integers defined recursively by:

i) (0,0)\in S
ii) If (a,b) \in S, then (a, b + 1) \in S, (a+1, b + 1) \in S,(a+2, b + 1) \in S

a) List the elements produced by 4 applications of these steps
b) using strong induction on the number of applications of the recursive set to show a <= 2b whenever (a, b) \in S
c) use structural induction for above

Homework Equations

n/a

The Attempt at a Solution

This is my first time doing proofs, barring the previous chapter 4.1 i finished last week and did fine in. This is one of my problem sets for my test on Wednesday, and I still have a lot of trouble proving anything with a recursive definition.
a) The first couple of elements are (0,1), (1,1), (2,1), and the second couple of elements are just the previous three processed by the recursive step, and (not listing redundant pairs) are (0,2), (1,2), (2,2), (3,2) and (4,2). This repeats for 3 and 4, etc.

Now the proof part baffles me. Induction seemed like a very formulaic process. I know that strong induction is simply just weak induction with the requirement that all the elements between the base case and arbitrary element 'k' hold true.

The book's answer was a lot simpler and straightforward than my own. Base is just 0 <= 0. next, it assumed an inductive hypothesis for k... and "on the number of applications of the recursive set" confuses me. Because the previous element (a,b) was obtained using less applications of the recursive step, a <= 2b? I just don't get how this coincides with the definition of strong induction.

For structural induction, it also wanted to show that b + 1 holds. It added the elements from the first application to the recursive step to show this (which... is + 1 to the step?), so essentially, it tried to prove the new elements generated by the recursive step by using the recursive step itself?!?

(also, i may have a few more problems i need help with, but this is the only hard odd problem that was assigned that had answers so I'm asking this first. i don't want to spam the board with topics, so should i just use this thread instead?)

 

[HallsofIvy]

I suspect that what they are doing is a recursion on the number of "steps" it takes to go from (0, 0) to (a, b). As you say, after "0" steps we start with (0, 0)- a= 0, b= 0 and certainly 0\le 2(0).

Now, the "induction step". We assume that all (a, b) obtained after k steps satisfy a\le 0. What do we get after k+1 steps?

Well, we get (a, b+1), (a+1, b+1), and (a+2, b+1). How do we prove the property we want holds for each of those?

For (a, b+1), we want to prove that a\le 2(b+1)= 2b+ 2. Well, that's easy to show. 0< 2 so adding a to both sides of that a< a+ 2. But adding 2 to both sides of a\le 2b we get a+2\le 2b+ 2. From that, a\le 2b+ 2.

For (a+ 1 , b+ 1), we want to prove that a+ 1\le 2(b+ 1) and for (a+2, b+1), we want to prove that a+ 2\le 2(b+ 1). I will leave those to you.

 

[DrWillVKN]

So k + 1 was proven using the inductive hypothesis a <= b, and its 'base' step? Then the second and third parts would follow the same procedure, with a < a + 1 <= a + 2 <= 2(b+1), and a < a + 2 <= a + 2 <= 2(b+1).

Only part I don't get is how strong and structural induction differ. And structural induction just seems like any kind of induction anyways, except that it uses the recursive step to prove the elements generated by that step.