Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

By defining these 3 matrices:

$\displaystyle M_1 = \begin{bmatrix} 1&0&0&0&0 \\ 1&1&0&0&0 \\ 1&1+x&1&0&0 \\ 1&1+x(1+x)&1+2x&1&0 \\ 1&1+x(1+x(1+x))&1+x(1+x)+x(1+2x)&1+3x&1 \end{bmatrix}$

$\displaystyle M_2 = \begin{bmatrix} 1&0&0&0&0 \\ x&1&0&0&0 \\ 1&x&1&0&0 \\ 0&1&x&1&0 \\ 0&0&1&x&1 \end{bmatrix}$

$\displaystyle M_3 = \begin{bmatrix} 1&1&1&1&1 \\ \frac{1}{2}(-1+x)x&1&1&1&1 \\ \frac{1}{2}(-1+x)x&\frac{1}{2}(-1+x)x&1&1&1 \\ 1&\frac{1}{2}(-1+x)x&\frac{1}{2}(-1+x)x&1&1 \\ 1&1&\frac{1}{2}(-1+x)x&\frac{1}{2}(-1+x)x&1 \end{bmatrix}$

and multiplying and dividing elementwise $M_1\cdot M_2 / M_3$ , we get the following matrix $A$:

$\displaystyle A = \begin{bmatrix} 1&0&0&0&0 \\ \frac{2}{-1+x}&1&0&0&0 \\ \frac{2}{(-1+x)x}&\frac{2(1+x)}{-1+x}&1&0&0 \\ 0&\frac{2(1+x(1+x))}{(-1+x)x}&\frac{2(1+2x)}{-1+x}&1&0 \\ 0&0&\frac{(2(1+x(1+x)+x(1+2x)))}{((-1+x)x)}&\frac{(2(1+3x))}{(-1 + x)}&1 \end{bmatrix}$

Then the matrix inverse of $A$ is a new matrix $B$ starting:

$\displaystyle B = \begin{bmatrix} 1&0&0 \\ \frac{-2}{-1 + x}&1&0 \\ (\frac{4}{(-1+x)^2} - \frac{2}{(-1+x)x} + \frac{4x}{(-1 + x)^2})&(\frac{-2}{-1+x} - \frac{2x}{-1+x})&1 \end{bmatrix}$

If we then calculate the ratios of the first column in matrix $B$ we get a sequence $c\;$:

$\displaystyle c = \frac {B(n,1)}{B(n+1,1)}, \; n=1,2,3\;...$

and if we define a sequence $b$:

$\displaystyle b = 1,\; 1+x,\; 1+2x,\; 1+3x \;...$

and multiply element-wise $c$ with $b$ and add $x$, we get a sequence $d\;$:

$\displaystyle d = x + b*c$

$\displaystyle d = \frac{1+x}{2}, \frac{x(2+x+x^2)}{1+x+2x^2}, \frac{1+x(6+x(7+2x(4+x)))}{2(1+x)(2+x+3x^2)}\;...$

My question is: Do the terms in this sequence $d$ tend to $\displaystyle \sqrt x\;$?

Example: $x=2\;$

$\displaystyle \frac{3}{2}, \frac{16}{11}, \frac{137}{96}, \frac{1642}{1157}, \frac{8429}{5950}, \frac{67952}{48001}, \frac{1509939}{1066976}, \frac{38701726}{27353183}, \frac{1124000429}{794502270}, \frac{36478904464}{25787223797} \;...$

$\displaystyle \frac{36478904464}{25787223797} = 1.41461$ which is close to $\displaystyle \sqrt 2 = 1.41421$

As a Mathematica program this is:

(*x is the value to calculate the square root of*)
Clear[x, t, tt, ttt, M1, M2, M3, A, B, b, c, n, k, i, j, 
  squarerootofx];
(*x=2; uncomment this to calculate sqrt of 2 or any other number*)
(*nn is size of matrix*)
nn = 5;
(*Variant of the Pascal triangle*)
t[n_, 1] = 1;
t[n_, k_] := t[n, k] = If[n > 1, t[n - 1, k - 1] + x*t[n - 1, k], 0];
M1 = Table[Table[t[i, j], {j, 1, nn}], {i, 1, nn}];
MatrixForm[M1]
tt[n_, k_] := 
  tt[n, k] = If[Or[n == k, n == k + 2], 1, If[n == k + 1, x, 0]];
M2 = Table[Table[tt[i, j], {j, 1, nn}], {i, 1, nn}];
MatrixForm[M2]
ttt[n_, k_] := 
  ttt[n, k] = 
   If[n == k, 1, If[Or[n == k + 1, n == k + 2], (x - 1)*x/2, 1]];
M3 = Table[Table[ttt[i, j], {j, 1, nn}], {i, 1, nn}];
MatrixForm[M3]
(*Elementwise multiplication and division of the 3 matrices*)
A = M1*M2/M3;
MatrixForm[A]
B = Inverse[A];
MatrixForm[B]
b = Range[1, x*(nn - 2) + 1, x]
c = Ratios[B[[All, 1]]]^-1;
d = squarerootofx = x + b*c
FullSimplify[squarerootofx]
N[squarerootofx];
share|improve this question
    
@t-laarhoven Your assumption about the notation is correct. I am used to the notation $T(n,k)$ that is often seen for matrices in Neil Sloane's OEIS, therefore I used $n$ as index. The Mathematica program should be correct however. Regarding an expression for the entries in matrix $B$, no I have not thought about that. And yes, I agree that there are easier ways to calculate $\sqrt x$. –  Mats Granvik Aug 24 '11 at 21:25
    
I am not quite sure I understand what the rule is for generating $M_1$. It looks like each row may be able to be generated recursively from the previous one(s); can you write down the relation? –  Willie Wong Aug 25 '11 at 1:55
    
@Willie Wong: Yes, $M_1$ is generated recursively. The recurrence is: $M_1 (n,1)=1\;$,$n>1:\;M_1 (n,k)=M_1(n-1,k-1)+x \cdot M_1(n-1,k)$ –  Mats Granvik Aug 25 '11 at 8:47
add comment

1 Answer 1

up vote 8 down vote accepted

This reminds me a lot of Do these series converge to the Mangoldt function? :-). I'm sure you have an explanation for how you managed to come up with this hypothesis in the first place, as you did in that case...

The sequence $d$ does indeed converge to $\sqrt x$. The solution of the recurrence

$$M_1 (n,k)=\begin{cases}1&k=1\\M_1(n-1,k-1)+x \cdot M_1(n-1,k)&k>1\\\end{cases}$$

is

$$ M_1(n,k)=\sum_{j=0}^{n-k}\binom{k+j-2}jx^j\;, $$

where the $k=1$ case works out if the binomial coefficient is generalized to $\binom{j-1}j$. But most of the matrix isn't used because of the zeros in $M_2$; so we will only need the cases $0\le n-k\le2$:

$$ \begin{eqnarray} M_1(n+2,n+2) &=& 1\;, \\ M_1(n+2,n+1) &=& 1+nx\;, \\ M_1(n+2,n+0) &=& 1+(n-1)x+\frac{n(n-1)}2x^2\;. \end{eqnarray} $$

Here and in the following $n\ge1$. Then the corresponding entries of $A$ are

$$ \begin{eqnarray} A(n+2,n+2) &=& 1\;, \\ A(n+2,n+1) &=& \frac2{x-1}(1+nx)\;, \\ A(n+2,n+0) &=& \frac2{x(x-1)}\left(1+(n-1)x+\frac{n(n-1)}2x^2\right)\;. \end{eqnarray} $$

The first column of the inverse $B$ is determined by the condition

$$\sum_{l=0}^2A(n+2,n+l)B(n+l,1)=0\;.$$

Since $A(n+2,n+2)=1$, we can directly solve for $B(n+2,1)$ to get a recurrence for $B$:

$$ \begin{eqnarray} B(n+2,1) &=& -A(n+2,n+1)B(n+1,1)-A(n+2,n)B(n,1) \\ &=& -\frac2{x-1}(1+nx)B(n+1,1) \\ && -\frac2{x(x-1)}\left(1+(n-1)x+\frac{n(n-1)}2x^2\right)B(n,1) \;. \end{eqnarray} $$

Dividing through by $B(n+1,1)$ yields

$$ \begin{eqnarray} \frac1{c(n+1)} &=& -A(n+2,n+1)-A(n+2,n)c(n) \\ &=& -\frac2{x-1}(1+nx) -\frac2{x(x-1)}\left(1+(n-1)x+\frac{n(n-1)}2x^2\right)c(n) \;, \end{eqnarray} $$

which is a one-term recurrence for $c$. With $d(n)=x+(1+(n-1)x)c(n)$, and thus

$$c(n)=\frac{d(n)-x}{1+(n-1)x}\;,$$

this yields a one-term recurrence for $d$:

$$ \frac{1+nx}{d(n+1)-x} = -\frac2{x-1}(1+nx) -\frac2{x(x-1)}\left(1+(n-1)x+\frac{n(n-1)}2x^2\right)\frac{d(n)-x}{1+(n-1)x} \;, $$

$$ \begin{eqnarray} \frac1{d(n+1)-x} &=& -\frac2{x-1}\left(1+\frac{1+(n-1)x+\frac12n(n-1)x^2}{(1+nx)(1+(n-1)x)}\frac{d(n)-x}x\right) \\ &=& -\frac2{x-1}\left(1+\gamma(n)\frac{d(n)-x}x\right) \;, \end{eqnarray} $$

where $\gamma(n)$ contains the dependence on $n$.

Now to get our bearings let's first see without full rigour what happens for large $n$. Then $\gamma(n)$ goes to $1/2$, and we get

$$ \begin{eqnarray} \frac1{d(n+1)-x} &=& -\frac2{x-1}\left(1+\frac12\frac{d(n)-x}x\right) \\ &=& \frac{d(n)+x}{x(1-x)} \;, \\ d(n+1) &=& x+\frac{x(1-x)}{d(n)+x} \\ &=& x\frac{d(n)+1}{d(n)+x}\;. \end{eqnarray} $$

Now we can look at what happens to the difference from $\sqrt x$:

$$ \begin{eqnarray} d(n+1)-\sqrt x &=& x\frac{d(n)+1}{d(n)+x}-\sqrt x \\ &=& \frac{x-\sqrt x}{d(n)+x}(d(n)-\sqrt x)\;. \end{eqnarray} $$

So if we could show that $d(n)$ is always positive, then we might be able to show that the sequence of the differences is dominated by a convergent geometric sequence. To make the approximation with $\gamma(n)=1/2$ rigorous, we will also need to bound $d(n)$ from above.

So let's go back to the full recurrence for $d$:

$$ d(n+1) = x-\frac{x-1}2\left(1+\gamma(n)\frac{d(n)-x}x\right)^{-1}\;. $$

Let's see how $\gamma(n)$ differs from its limit:

$$ \begin{eqnarray} \gamma(n)-\frac12 &=& \frac{1+(n-1)x+\frac12n(n-1)x^2}{(1+nx)(1+(n-1)x)}-\frac12 \\ &=& \frac12\frac{1-x}{(1+nx)(1+(n-1)x)} \end{eqnarray} $$

Thus we have $0<\gamma(n)\lt1/2$ for $x\gt1$ and $1/2\lt\gamma(n)\lt1$ for $x\lt1$. Also note that for $d(n)>0$ we have

$$1+\gamma(n)\frac{d(n)-x}x\gt1+\gamma(n)\frac{-x}x=1-\gamma(n)\gt0\;.$$

Now first assume $x\gt1$. Then for $d(n)\gt0$,

$$ \begin{eqnarray} d(n+1) &\gt& x-\frac{x-1}2\left(1+\gamma(n)\frac{0-x}x\right)^{-1} \\ &=& x-\frac{x-1}2\left(1-\gamma(n)\right)^{-1} \\ &\gt& x-\frac{x-1}2\left(\frac12\right)^{-1} \\ &=& x-(x-1) \\ &=& 1\;. \end{eqnarray} $$

On the other hand, for $d(n)\lt x$,

$$ \begin{eqnarray} d(n+1) &\lt& x-\frac{x-1}2\left(1+\gamma(n)\frac{x-x}x\right)^{-1} \\ &=& x-\frac{x-1}2 \\ &=& \frac{x+1}2\;. \end{eqnarray} $$

Since $1\lt d(1)=(x+1)/2\lt x$, it follows that $1\lt d(n)\le(x+1)/2\lt x$ for all $n$.

Now assume $x<1$. Then $d(n+1)\gt x$. On the other hand, for $d(n)\gt x$,

$$ \begin{eqnarray} d(n+1) &\lt& x-\frac{x-1}2\left(1+\frac12\frac{d-x}x\right)^{-1} \\ &\lt& x-\frac{x-1}2\left(1+\frac12\frac{-x}x\right)^{-1} \\ &=& x-\frac{x-1}2\left(\frac12\right)^{-1} \\ &=& x-(x-1) \\ &=& 1\;. \end{eqnarray} $$

Since $x\lt d(1)=(x+1)/2\lt1$, it follows that $x\lt d(n)\lt1$ for all $n$.

Now we have all the ingredients for the proof of convergence. Let's put $\gamma(n)=\frac12(1+\epsilon(n))$, with $\epsilon(n)\to0$ as $n\to\infty$, so

$$ \begin{eqnarray} d(n+1) &=& x-\frac{x-1}2\left(1+\frac12(1+\epsilon(n))\frac{d(n)-x}x\right)^{-1} \\ &=& x-\frac{x-1}2\frac{x}{x+\frac12(1+\epsilon(n))(d(n)-x)} \\ &=& \frac{x(d(n)+x+\epsilon(n)(d(n)-x))-(x-1)x}{d(n)+x+\epsilon(n)(d(n)-x)} \\ &=& \frac{x(d(n)+1)+\epsilon(n)x(d(n)-x)}{d(n)+x+\epsilon(n)(d(n)-x)}\;, \end{eqnarray} $$

and consider the difference from $\sqrt x$ again:

$$ \begin{eqnarray} d(n+1)-\sqrt x &=& \frac{x(d(n)+1)+\epsilon(n)x(d(n)-x)}{d(n)+x+\epsilon(n)(d(n)-x)}-\sqrt x \\ &=& \frac{(x-\sqrt x)(d(n)-\sqrt x+\epsilon(n)x(d(n)-x))}{d(n)+x+\epsilon(n)(d(n)-x)} \\ &=& \frac{(x-\sqrt x)(1+\epsilon(n)x(d(n)+\sqrt x))}{d(n)+x+\epsilon(n)(d(n)-x)}(d(n)-\sqrt x) \;. \end{eqnarray} $$

Since $d(n)$ is bounded and positive (and $x$ is constant and positive), we have

$$ \limsup_{n\to\infty}\left|\frac{(x-\sqrt x)(1+\epsilon(n)x(d(n)+\sqrt x))}{d(n)+x+\epsilon(n)(d(n)-x)}\right| =\limsup_{n\to\infty}\left|\frac{x-\sqrt x}{d(n)+x}\right| \le\left|\frac{x-\sqrt x}x\right|\lt1\;, $$

and so the sequence of the differences is dominated by a convergent geometric sequence. That completes the proof.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.