I got this question today and I'm nowhere near the solution,Given a sequence of real numbers (X1, X2, ..,Xn). write an algorithm as efficient there is, that finds the number of strictly increasing sub-sequences for every index j, that end with Xj.My solution should include a recurrence formula that solves this problem in O(n^2) and a correctness proof, I was only able to solve it using a nested for loop and I'm not sure if there's an O(n^2) recursion solution.List a[1n] <- [11] For j= 1 to n    For i= 1 to j-1       If xi<xj then          a[i]= a[j]+a[i]; 
Using dynamic programming to find the number ofl increasing subsequences
algorithms;dynamic programming;recursion;correctness proof
The recursive equivalent of what you wrote is:function S(j) is  r <- 1  For i <- 1 to j-1    if xi<xj then      r <- r+S(i)  return rIt is very similar to what you wrote, except that a[1] is replaced byS(i), i.e., a recursive call to the function, since it is the functionthat is supposed to compute the number of sequences that you store in a[i]. The array a is used to rememberprevious results, and the new result you are computing is obtainedusing the previous results.This array is no longer needed, as it is replaced by the memoization of the dynamic programming interpretation of the recursive function. If I understood correctly what you are asking.Now, to do the proof, you should explain why computing in this way iscorrect.This works with the same costs as your algorithm, provided the recursion is interpreted with dynamic programming memomization, and you should beable to prove it easily.Of course standard recursive execution of the function, without memoization of results, is a lot more costly.