A subset T of the integers is defined recursively as follows: Base case: 2 ∈ T Recursive rule: if k ∈ T, then k + 5 ∈ T This problem asks you to prove that T is exactly the set of integers that can be expressed as 5m+2, where m is a non-negative integer. In other words, you will prove that x ∈ T if and only if x = 5m+2, for some non-negative integer m. The two directions of the "if and only if" are proven separately. (a) Use structural induction to prove that if k ∈ T, then k = 5m + 2, for some non-negative integer m.

Question

Emily Guerrero

Mathematics

19 September, 15:22

A subset T of the integers is defined recursively as follows: Base case: 2 ∈ T Recursive rule: if k ∈ T, then k + 5 ∈ T This problem asks you to prove that T is exactly the set of integers that can be expressed as 5m+2, where m is a non-negative integer. In other words, you will prove that x ∈ T if and only if x = 5m+2, for some non-negative integer m. The two directions of the "if and only if" are proven separately. (a) Use structural induction to prove that if k ∈ T, then k = 5m + 2, for some non-negative integer m.

+3

Answers (1)

Know the Answer?

Ben Daniel · Answer 1

Step-by-step explanation:

We must prove the statement for the base case, and then state our induction hypothesis.

For the base case, note that 2 = 5*0 + 2, so since 0 is a non-negative integer, it is true for 0.

We want to see that if k is in T and has a the property k = 5m+2 for an non negative integer, then the next element of T in the list, i. e k+5 has also this property.

Suppose that for an integer k in T we have an non negative integer m such that k = 5m+2. We have that k+5 = 5m+2 + 5 = 5 (m+1) + 2. So, since m+1 is also a non negative integer, we have proved the claim using structural induction.