- Thread starter Ryan$
- Start date

- Joined
- Jan 27, 2012

- Messages
- 4,787

(i) Suppose i= 1. Then there exist NO "j" with j< i so there is no j such that "\(\displaystyle 1\le j< i\)". By the second line in the definition, s(1)= 1.

(ii) Suppose i= 2. The only "j"< 2 is j= 1. But now we have to look at M[1] and M[2]. There exist j such that "\(\displaystyle 1\le j< i\), j= 1. Is it true that "M[1]< M[2]"? Is it is then s(2)= 1+ s(1)= 2. If not, then s(2)= 1.

(iii) Suppose i= 3. Then "j< 3" is true for j= 1 and j= 2. So now we look at M[1], M[2], and M[3]. IF it is true that M[1]< M[3] then we look at 1+ s(1)= 2. IF it is true that M[2]< M[3] then we look at 1+ s(2) which is either 2 or 3 depending upon what happened is (ii). If both those inequalities are true then s(3) is 1 plus the larger of those, either 3 or 4. If only one of the inequalities is true then s(3) is 1 plus the "s" value for which it is true. If neither inequality is true then s(3)= 1.

Continue in that way. Everything depends on the value in the array M.

" and "M[j]" are specific numbers in that array. With "recursive" formulas, you need to go through the indices, step by step, starting at 1.

(i) Suppose i= 1. Then there exist NO "j" with j< i so there is no j such that "\(\displaystyle 1\le j< i\)". By the second line in the definition, s(1)= 1.

(ii) Suppose i= 2. The only "j"< 2 is j= 1. But now we have to look at M[1] and M[2]. There exist j such that "\(\displaystyle 1\le j< i\), j= 1. Is it true that "M[1]< M[2]"? Is it is then s(2)= 1+ s(1)= 2. If not, then s(2)= 1.

(iii) Suppose i= 3. Then "j< 3" is true for j= 1 and j= 2. So now we look at M[1], M[2], and M[3]. IF it is true that M[1]< M[3] then we look at 1+ s(1)= 2. IF it is true that M[2]< M[3] then we look at 1+ s(2) which is either 2 or 3 depending upon what happened is (ii). If both those inequalities are true then s(3) is 1 plus the larger of those, either 3 or 4. If only one of the inequalities is true then s(3) is 1 plus the "s" value for which it is true. If neither inequality is true then s(3)= 1.

Continue in that way. Everything depends on the value in the array M.

thanks!!