1
$\begingroup$

Provided a recurrence relationship, I converted the equation assuming $T(n) = r(n)$, and found the roots to the quadratic equation.

root 1: $r_1 = 2+\sqrt{3}$

root 2: $r_2 = 2-\sqrt{3}$

Resulting in the equation with the form $T(n) = c_1(r_1)^n + c_2(r_2)^n$

$$T(1): 1 = c_1(2+\sqrt{3})^1 + c_2(2-\sqrt{3})^1$$

$$T(3): 3 = c_1(2+\sqrt{3})^3 + c_2(2-\sqrt{3})^3$$

How do I go about solving for $c_1$ and $c_2$ in this particular instance. I'm used to an initial condition being 0, eliminating one of the $c$'s, then plugging the remaining into the second equation. But I am stuck here.

My end goal is to result with a closed form solution to a recurrence relationship from $T(n)$.

$\endgroup$
1
  • $\begingroup$ Solve those two simultaneous linear equations for the c's. $\endgroup$ Commented Nov 14, 2018 at 4:19

1 Answer 1

Reset to default
1
$\begingroup$

For brevity, take

\begin{align} \alpha &= 2+\sqrt{3} \\ \beta &= 2-\sqrt{3} \\ A &= c_1 \\ B &= c_2 \end{align}

Now,

\begin{align} \alpha+\beta &= 4 \\ \alpha-\beta &= 2\sqrt{3} \\ \alpha \beta &= 1 \\ A\alpha+B\beta &= 1 \tag{1} \\ A\alpha^3+B\beta^3 &= 3 \tag{2} \end{align}

$(2)-\beta^2 \times (1)$,

\begin{align} A\alpha (\alpha^2-\beta^2) &= 3-\beta^2 \\ A\alpha (\alpha+\beta)(\alpha-\beta) &= 3-(4-4\sqrt{3}+3) \\ 8A\alpha\sqrt{3} &= 4(\sqrt{3}-1) \\ A &= \frac{\sqrt{3}-1}{2\sqrt{3}(2+\sqrt{3})} \\ &= \frac{(\sqrt{3}-1)(2-\sqrt{3})}{2\sqrt{3}} \\ &= \frac{9-5\sqrt{3}}{6} \end{align}

$\alpha^2 \times (1)-(2)$,

\begin{align} B\beta (\alpha^2-\beta^2) &= \alpha^2-1 \\ B\beta (\alpha+\beta)(\alpha-\beta) &= (4+4\sqrt{3}+3)-3 \\ 8B\beta\sqrt{3} &= 4(\sqrt{3}+1) \\ B &= \frac{9+5\sqrt{3}}{6} \end{align}

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.