contestada

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.

Respuesta :

Answer:

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.

facundo3141592

We need to prove the statement:

" x ∈ T, if and only if x = 5m + 2, for a positive integer m"

First, we define T as:

2 ∈ T

rule:

If k ∈ T, then  k + 5 ∈ T.

Particularly, we know that 2 belongs to T, then:

2 + 5 ∈ T

(2 + 5) + 5 ∈ T

So we can see that all the numbers that belong to T are of the form:

2 + m*5

Here we proved the →, now we need to go in the other direction.

We start by assuming that x = 2 + m*5, we want to see that x belongs to T.

So, if we define m = 0, then it is trivial that x belongs to T.

And because m is a positive integer, having x = 2 + m*5 means that we increased by 5 m times.

And each of these increases also belongs to T, by definition of T, then all the x of the form " x = 2 + m*5" must belong to T.

If you want to learn more, you can read:

https://brainly.com/question/11827486

Otras preguntas