Induction on sequence

Hi,


I'll go strait to the point:

I have an array of values (it is a problem from CS but simplified) like :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 ...

---

indexing starts from 0. so A[0] = 1

rule by which the array if filled is : A[i+1] = A[i] +1

Question is :

Will the difference between two consecutive values always be 1.


I decided to prove this by induction on i. So, for i=0 we have A[i+1] -A[i] = A[i] + 1 -A[i] = 1 as expected. Then for i>0 according to the inductive hypothesis if p=0..k, A[q+1]-A[q] = 1 and for q = 1..k+1 we have A[q+1]-A[q] = 1 then it follows that for all i = 0..k+1, A[i+1]-A[i] = 1.


Does this make any sense ??

Thank you

Hey baxy77bax.

You can do this if you want but you can just re-arrange your relationship and assume that if it holds for all i then the relationship is true.

Induction statements are usually defined for things that vary but in your case you have specified that A[i+1] - A[i] = 1, where-as many inductive statements look at things that vary (like say A[i+1] - A[i] = i^2 + 2i - 1 for example).

Quote:

---

Originally Posted by baxy77bax

rule by which the array if filled is : A[i+1] = A[i] +1

---

Does it follow that A[i + 1] - A[i] = 1? Hmm, let's ask an elementary school student who learned how to move terms from one side of an equation into the other.

Formally speaking, chiro is right that your induction argument does not use the induction hypothesis, so it is a direct proof (and trivial at that).