2
$\begingroup$

This is a Structural Induction proof.

I don't want the solution, just some help in the right direction. I know normally in structural induction proofs, you use your base case, with the recursive step to get to the rest of the set, but x2 and y2 are required, so I don't know how to go about getting other elements. Also, for the actual proving, the step where we prove for an arbitrary k, what do you even begin with to test that k+1 works?

I am given :

S is the set of ordered pairs of integers, such that:

    Base Step : (2,5) ∈ *S*
    Recursive Step: If (x1,x2) ∈ S and (y1,y2) ∈ S, then (x1y1,x2+y2) ∈ *S*

Using structural induction prove every element of S is of the form (2^k,5k), k is a positive integer

Thanks for any help you can give

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ This newsgroup is for research-level questions. Perhaps this might be more appropriate in math.stackexchange instead? $\endgroup$ – Arturo Magidin Apr 8 '16 at 17:22
0
$\begingroup$

Assume $S_n=\{ (2^k,5k) | k<=n \}$. Then show that $S_{n+1}$ contains only elements of the form $(2^k,5k)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the answer. Just a follow up question.... How can you check that they are of the same form with just the simple "assume k is some arbitrary number approach"? I feel like I am just missing a piece of information, or am just overthinking this super freakin hard. If you just throw the n in there, you would just end up with (2^n,5n) and I don't feel like that really proves anything. $\endgroup$ – Dozi Apr 8 '16 at 17:30
  • $\begingroup$ you stated you didn't want the solution, but consider how many elements of $S_{n+1}$ are there $\endgroup$ – JMP Apr 8 '16 at 17:32

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.