MHB For j >1 the first 2^j digits are correct

[mathmari]

Hey!

We have the iteration formula $$x_{j+1}=2x_j-3x_j^2$$ and using the starting point $x_0=0.3$ we get the following approximations for $\frac{1}{3}$ :

\begin{align*}&x_1=2x_0-3x_0^2=2\cdot 0.3-3\cdot 0.3^2=0.33 \\ &x_2=2x_1-3x_1^2=2\cdot 0.33-3\cdot 0.33^2=0.3333 \\ &x_3=2x_2-3x_2^2=2\cdot 0.3333-3\cdot 0.3333^2=0.33333333\end{align*}

Now I want to show that for $j\geq 1$ the first $2^j$ digits of $x_j$ are correct for $\frac{1}{3}$.

It is $\frac{1}{3}=0.33333333333333333333333333\ldots$.

The approximation $x_1$ has the first $2=2^1$ digits correct.

The approximation $x_2$ has the first $4=2^2$ digits correct.

The approximation $x_3$ has the first $8=2^3$ digits correct.To show that it holds for $j\geq 1$ do we have to use induction? :unsure:

 

[I like Serena]

Hi mathmari!

Induction seems to be the way to go yes.
So we need to write $x_j$ in terms of $2^j$. Can we find such an expression?

 

[mathmari]

Induction seems to be the way to go yes.
So we need to write $x_j$ in terms of $2^j$. Can we find such an expression?

As a power of $10$ we get \begin{align*}x_j&=\sum_{i=1}^{2^j}\frac{3}{10^i}=3\cdot \sum_{i=1}^{2^j}\frac{1}{10^i}=3\cdot \left (\sum_{i=0}^{2^j}\frac{1}{10^i}-1\right )=3\cdot \frac{\frac{1}{10^{2^j+1}}-1}{\frac{1}{10}-1}-3=3\cdot \frac{\frac{1}{10^{2^j+1}}-1}{-\frac{9}{10}}-3=-\frac{10}{9}\cdot 3\cdot \left (\frac{1}{10^{2^j+1}}-1\right )-3=-\frac{10}{3}\cdot \left (\frac{1}{10^{2^j+1}}-1\right )-3=-\frac{10}{3}\cdot \frac{1}{10^{2^j+1}}+\frac{10}{3}-3\\ & =-\frac{1}{3}\cdot \frac{1}{10^{2^j}}+\frac{1}{3}\end{align*} right?
So by induction on $j$ we get:

Base Case: For $j=1$ we get the desired result, as seen.

Inductive Hypothesis: We suppose that the formula is true for $j=k$, i.e. $\displaystyle{x_k=-\frac{1}{3}\cdot \frac{1}{10^{2^k}}+\frac{1}{3}}$.

Inductive Step: We want to show that the formula is true also for $j=k+1$ : \begin{align*}x_{k+1}=2x_k-3x_k^2\ &\overset{(IH)}{=} \ 2\left (-\frac{1}{3}\cdot \frac{1}{10^{2^k}}+\frac{1}{3}\right )-3\left (-\frac{1}{3}\cdot \frac{1}{10^{2^k}}+\frac{1}{3}\right )^2\\ & =-\frac{2}{3}\cdot \frac{1}{10^{2^k}}+2\cdot \frac{1}{3}-3\left (\frac{1}{3^2}\cdot \frac{1}{10^{2^{k+1}}}-2\cdot \frac{1}{3}\cdot \frac{1}{10^{2^k}}\cdot \frac{1}{3}+\frac{1}{3^2}\right ) \\ & =-\frac{2}{3}\cdot \frac{1}{10^{2^k}}+2\cdot \frac{1}{3}-\frac{1}{3}\cdot \frac{1}{10^{2^{k+1}}}+2\cdot \frac{1}{10^{2^k}}\cdot \frac{1}{3}-\frac{1}{3}\\ & =\frac{1}{3}-\frac{1}{3}\cdot \frac{1}{10^{2^{k+1}}} \end{align*}

So we get that this hold for every $j\geq 1$ (Happy)

 

[I like Serena]

As a power of $10$ we get \begin{align*}x_j&=-\frac{1}{3}\cdot \frac{1}{10^{2^j}}+\frac{10}{3}\end{align*} right?

Suppose we substitute $j=1$. Then we should get $x_1=0.33$ yes?
$$x_1=-\frac{1}{3}\cdot \frac{1}{10^{2^1}}+\frac{10}{3}=-\frac{1}{300}+\frac{10}{3}=3.33$$
That's not correct is it?

 

[mathmari]

Suppose we substitute $j=1$. Then we should get $x_1=0.33$ yes?
$$x_1=-\frac{1}{3}\cdot \frac{1}{10^{2^1}}+\frac{10}{3}=-\frac{1}{300}+\frac{10}{3}=3.33$$
That's not correct is it?

I found my error! I edited my previous post and the correct result came out!