# Discrete Math Question: Induction. Define a sequence recursively as follows. x_1=1 and for n in N, x_{n+1}=sqrt{(x_n)^2+1//(x_n)^2}

Discrete Math Question: Induction
Define a sequence recursively as follows. ${x}_{1}=1$ and for $n\in N,{x}_{n+1}=\sqrt{\left({x}_{n}{\right)}^{2}+1/\left({x}_{n}{\right)}^{2}}$
Prove using mathematical induction that for all $n\in N$, $1\le {x}_{n}\le \sqrt{n}$
You can still ask an expert for help

## Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

tun1t2j
Step 1
Base Case, clear.
Induction Hypothesis: Assume that $1\le {x}_{n}\le \sqrt{n}$ for all $n\le m$.
Step 2
Induction step: Consider ${x}_{m}$. We note that
${x}_{m}=\sqrt{\left({x}_{m-1}{\right)}^{2}+\frac{1}{\left({x}_{m-1}{\right)}^{2}}}\le \sqrt{\left({x}_{m-1}{\right)}^{2}+1}\le \sqrt{\left(\sqrt{m-1}{\right)}^{2}+1}=\sqrt{m}$
The "$1\le$" portion is easier and is left to you to figure out. Notice that we did not need to find a closed form formula.