0

I already showed how to solve the following recurrence? $t(n)=[4-t(n-1)]^{-1}$ that for $T_0 \neq 0$ or $T_k \neq 0$ we have,

$$T_{n}=\frac{c_1(2+\sqrt{3})^{n-1}+c_2(2-\sqrt{3})^{n-1}}{c_1(2+\sqrt{3})^n+c_2(2-\sqrt{3})^n}$$

But this does not work for $T_0=0$ what should I do. I'm thinking taking the limit as $T_0 \to 0$ but not sure how to do it.

Community
  • 1
Ahmed S. Attaalla
  • 18,518
  • 1
    I wonder if your expression is for $T_{n-1}$ instead of $T_n$. – Claude Leibovici Feb 03 '17 at 08:08
  • 1
    Just start from $T_1=\frac14$ instead of $T_0=0$; the method you linked to should work the same. – Greg Martin Feb 03 '17 at 08:22
  • I tried that it didn't work. I think the problem is that if $T_1=\frac{1}{4}$ or even else then the recurrence can go trace back to a time where you divided by $0$. I plugged the recurrence into wolfram, It seems as if $T_k=0$ for any $k \in \mathbb{Z}$ the formula different. This seems pretty wierd to me. @GregMartin – Ahmed S. Attaalla Feb 03 '17 at 14:49
  • If you redefine $c_1 \mapsto (2+\sqrt{3})c_1$ and $c_2 \mapsto (2-\sqrt{3})c_2$. You will see that my formula is the same as wolfram alphas, at least if we don't run into the problem that $T_s=0$ for some $s \in \mathbb{Z}$ @ClaudeLeibovici – Ahmed S. Attaalla Feb 03 '17 at 15:42
  • 3
    Possible duplicate of how to solve the following recurrence? $t(n)=[4-t(n-1)]^{-1}$ – Did Feb 03 '17 at 18:15
  • The case $T_0=0$ is perfectly all right, see the page this one duplicates. – Did Feb 03 '17 at 18:15
  • But there is a problem, when you do the system the system of equations for the initial condition you get $c_1=c_2=0$. And btw, the link you gave is my answer, I just have a question on when $T_0=0$ @Did – Ahmed S. Attaalla Feb 03 '17 at 20:55
  • Let me suggest to read very carefully every part of the page linked. If you do, you might see that the case $T_0=0$ is fully solved there. – Did Feb 03 '17 at 21:44

2 Answers2

1

Note you can set $c_1=1$ always, since $c_1$ and $c_2$ can be scaled by the same number. Also set $\alpha=2+\sqrt3$ and $\beta=2-\sqrt3$. When I solve $$ \frac{\alpha^{0-1}+c_2\beta^{0-1}}{\alpha^{0}+c_2\beta^{0}}=k $$ for $c_2$, I get $$ c_2 = \frac{\sqrt3+k-2}{\sqrt3+k+2}. $$ So we can certainly try setting $c_2 = \frac{\sqrt3-2}{\sqrt3+2} = -\beta^2$ and see what happens. And sure enough, the formula $$ T_n = \frac{\alpha^{n-1}-\beta^2\beta^{n-1}}{\alpha^{n}-\beta^2\beta^{n}} = \frac{\alpha^{n-1}-\beta^{n+1}}{\alpha^{n}-\beta^{n+2}} $$ does seem to give the sequence accurately in the case $T_0=0$.

Greg Martin
  • 78,820
  • Do you know why I get $c_1,c_2=0$ when I try to make a system for it. – Ahmed S. Attaalla Feb 03 '17 at 20:45
  • I really don't get why dividing by $c_2$ top and bottom clears the issue of $c_1=c_2=0$. And all other answers are unreadable to me. Can you please explain. – Ahmed S. Attaalla Feb 03 '17 at 22:42
  • @AhmedS.Attaalla Once again, please read this: http://math.stackexchange.com/questions/2124614/how-to-solve-the-following-recurrence-tn-4-tn-1-1#comment4375644_2124614 – Did Feb 04 '17 at 07:54
1

Here is my answer :-

Note that $t(0)=0=0/1$

$t(1)=1/4$

$t(2)=4/15$

$t(3)=15/36$

Or, $t(1)=\frac{1}{4-0}$

$t(2)=\frac{1}{\frac{16}{4}-\frac{1}{4}}$

$t(3)=\frac{1}{\frac{60}{15}-\frac{4}{15}}$

...

So $t(n)=\frac{a_{n-1}}{an}=\frac{a_{n-1}}{4a_{n-1}-a_{n-2}}$ with $a_{0}=0 \space and\space a_{1}=1$

We have $a_{n}=4a_{n-1}-a_{n-2}$ which is equivalent to $p(x)=x^2-4x+1$

We find that the roots of this equation are $2+\sqrt(3) \space and\space 2 - \sqrt(3)$

Let's say $r_{1}=2+\sqrt(3)$ and $r_{2}=2-\sqrt{3}$

So $a(n)=c_{1}(2+\sqrt{3})^n+c_{2}(2-\sqrt{3})^n$

For n=0, we get $c_{1}+c_{2}=0$

For n=1, we get $c_{2}=\frac{-1}{2\sqrt{3}}$

Hence,a(n)=$\frac{1}{2\sqrt{3}}(2+\sqrt{3})^n-\frac{1}{2\sqrt{3}}(2-\sqrt{3})^n$

So T(n)=$\frac{\frac{1}{2\sqrt{3}}(2+\sqrt{3})^{n-1}-\frac{1}{2\sqrt{3}}(2-\sqrt{3})^{n-1}}{\frac{1}{2\sqrt{3}}(2+\sqrt{3})^n-\frac{1}{2\sqrt{3}}(2-\sqrt{3})^n}$

=$\frac{(2+\sqrt{3})^{n-1}-(2-\sqrt{3})^{n-1}}{(2+\sqrt{3})^n-(2-\sqrt{3})^n}$

Zok
  • 209
  • 1
  • 8