patternMinor
Solving the recurrence $T(n)=T(n−1)/T(n−2)$
Viewed 0 times
solvingtherecurrence
Problem
How can I solve this?
I saw Solving the recurrence $T(n)=T(n-1)*T(n-2)$ but I don't know how I can apply it to $T(n)=T(n-1)/T(n-2)$?
I saw Solving the recurrence $T(n)=T(n-1)*T(n-2)$ but I don't know how I can apply it to $T(n)=T(n-1)/T(n-2)$?
Solution
Then assume $T(0) = a, T(1)=b$ such as $a \neq 0$ and $b \neq 0$.
You could write down first few terms and deduce the pattern
$$T(0)= a$$
$$T(1)= b$$
$$T(2)= \frac{T(1)}{T(0)} = \frac{b}{a}$$
$$T(3)= \frac{T(2)}{T(1)} = \frac{b/a}{b} = \frac{1}{a}$$
$$T(4)= \frac{T(3)}{T(2)} = \frac{1/a}{b/a} = \frac{1}{b}$$
$$T(5)= \frac{T(4)}{T(3)} = \frac{1/b}{1/a} = \frac{a}{b}$$
$$T(6)= \frac{T(5)}{T(4)} = \frac{a/b}{1/b} = a = T(0)$$
$$T(7)= \frac{T(6)}{T(5)} = \frac{a}{a/b} = b = T(1)$$
$$...$$
Thus the values of $T(n)$ repeat with period of $6$.
You could write down first few terms and deduce the pattern
$$T(0)= a$$
$$T(1)= b$$
$$T(2)= \frac{T(1)}{T(0)} = \frac{b}{a}$$
$$T(3)= \frac{T(2)}{T(1)} = \frac{b/a}{b} = \frac{1}{a}$$
$$T(4)= \frac{T(3)}{T(2)} = \frac{1/a}{b/a} = \frac{1}{b}$$
$$T(5)= \frac{T(4)}{T(3)} = \frac{1/b}{1/a} = \frac{a}{b}$$
$$T(6)= \frac{T(5)}{T(4)} = \frac{a/b}{1/b} = a = T(0)$$
$$T(7)= \frac{T(6)}{T(5)} = \frac{a}{a/b} = b = T(1)$$
$$...$$
Thus the values of $T(n)$ repeat with period of $6$.
Context
StackExchange Computer Science Q#83402, answer score: 5
Revisions (0)
No revisions yet.