- #1
DrWillVKN
- 22
- 0
Homework Statement
Let S be subset of set of ordered pairs of integers defined recursively by:
i) (0,0)[tex]\in[/tex] S
ii) If (a,b) [tex]\in[/tex] S, then (a, b + 1) [tex]\in[/tex] S, (a+1, b + 1) [tex]\in[/tex] S,(a+2, b + 1) [tex]\in[/tex] 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) [tex]\in[/tex] 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?)