# Help With an (structural) Induction proof on ordered pair

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

Assume $S_n=\{ (2^k,5k) | k<=n \}$. Then show that $S_{n+1}$ contains only elements of the form $(2^k,5k)$.
• you stated you didn't want the solution, but consider how many elements of $S_{n+1}$ are there – JMP Apr 8 '16 at 17:32