We define the recursive sequence by `x_(1) = 1` , `x_(n+1) = sqrt(x_(n) + 1)` and how do we show that `x_(n)` is strictly monotonically increasing?
Can we also show that `x_(n)` is bound from above by 2 and then, which is the limit for` n-> oo`
First, we need to establish that `ninNN` in order to solve this probelm properly. Now, it is kind of implied, but let's just go ahead and say it to make sure!
The easiest way to do this is to show that for any `n` that
`x_(n+1) - x_n > 0`
Well, we already know that `x_(n + 1) = sqrt(x_n + 1)`
So, we can substitute this expression into the above inequality:
`sqrt(x_n+1) - x_n > 0`
This may be difficult to prove explicitly (especially because it is often not true in general!).
Let's prove this, then, by induction. Remember, to prove by induction, we need to prove:
1) The base case (that it holds true for n = 1)
2) The inductive case (if true for n = k, then true for n = k+1)
Let's start wih the base case:
`sqrt(x_1+1) - x_1 >? 0`
We substitute `1` for `x_1` due to our definition above:
`sqrt(1+1) - 1`
Now, we just evaluate the square root and simplify:
`sqrt(2) - 1 ~~ 1.414 - 1 = 0.414`
Now, clearly, 0.414 > 0, so we have proven our base case! Let's move on.
Let's assume the following:
`sqrt(x_k + 1) - x_k > 0`
Now, let's prove that the inequality holds for `x_(k+1)`
Our inequality becomes:
`sqrt(x_(k+1) + 1) - x_(k+1) >? 0`
Recall, based on the recursive function, that `x_(k+1) = sqrt(x_k + 1)`
We can now substitute the above expression for `x_(k+1)`
`sqrt(sqrt(x_k+1) + 1) - sqrt(x_k + 1) >? 0`
Well, this looks like fun (sarcasm). But we can do something clever here. We can multiply both sides of this inequality by the following expression without changing the inequality because it can never be negative (due to the range/domain of the square root function):
`sqrt(sqrt(x_k+1) + 1) + sqrt(x_k+1)`
Multiplying by this expression (recall `(a-b)(a+b) = a^2-b^2`):
`sqrt(x_k+1) + 1 - (x_k + 1) > ?0`
`sqrt(x_k +1) + 1 - x_k - 1 >? 0`
`sqrt(x_k + 1) - x_k >? 0`
Well, look at that, our inductive assumption! We can finally get rid of that annoying question mark:
`sqrt(x_k + 1) - x(k) > 0`
Therefore, we have just proven that:
`sqrt(x_(k+1) + 1) - x(k+1) > 0`
Therefore, we know that the recursive function is monotonically increasing for all n.
I hope that helps!