Question

Define a Q-sequence recursively as follows.

B.	x, 4 − x is a Q-sequence for any real number x.
R.	If x1, x2,   , xj and y1, y2,   , yk are Q-sequences, so is
	x1 − 1, x2,   , xj, y1, y2,   , yk − 3.

Use structural induction (i.e., induction on the recursive definition) to prove that the sum of the numbers in any Q-sequence is 4.

Base Case: Any Q-sequence formed by the base case of the definition has sum

x + (4 − x) =  .

Inductive Hypothesis: Suppose as inductive hypothesis that

x₁, x₂,   , x_j

and

y₁, y₂,   , y_k

are Q-sequences, each of which sums to 4.

Inductive Step: The Q-sequence formed by the recursive part of the definition is

x1 − 1, x2,   , xj, y1, y2,   , yk − 3	=	x1 + x2 +    + xj −  + y1 + y2 +    + yk − 3
	=	4 − 1 + 4 −
	=	, as required.

Answer 1