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