I have no clue how to solve a recurrence relation which contains ceiling function
How can I solve this:
Equation: $a_n=0.2*\lceil a_{n-1} \rceil$ with $a_0 = 0$ and $a_1 = 20$
?
Thanks!
Solve reccurence relation with ceiling
ceiling-and-floor-functionsrecurrence-relations
Related Solutions
[Math] How to solve the recurrence relation $T(n) = T(\lceil n/2\rceil) + T(\lfloor n/2\rfloor) + 2$
As mentioned in comment, the first two conditions $T(1) = 0, T(2) = 1$ is incompatible with the last condition $$\require{cancel} T(n) = T(\lfloor\frac{n}{2}\rfloor) + T(\lceil\frac{n}{2}\rceil) = 2\quad\text{ for } \color{red}{\cancelto{\;\color{black}{n > 2}\;}{\color{grey}{n \ge 2}}} \tag{*1}$$ at $n = 2$. We will assume the condition $(*1)$ is only valid for $n > 2$ instead.
Let $\displaystyle\;f(z) = \sum\limits_{n=2}^\infty T(n) z^n\;$ be the generating function for the sequence $T(n)$. Multiply the $n^{th}$ term of $(*1)$ by $z^n$ and start summing from $n = 3$, we obtain:
$$\begin{array}{rrl} &f(z) - z^2 &= T(3) z^3 + T(4) z^4 + T(5) z^5 + \cdots\\ &&= (T(2) + 2)z^3 + (T(2) + T(2) + 2)z^4 + (T(2)+T(3)+2)z^5 + \cdots\\ &&= (1+z)^2 ( T(2)z^3 + T(3)z^5 + \cdots) + 2(z^3 + z^4 + z^5 + \cdots)\\ &&= \frac{(1+z)^2}{z}f(z^2) + \frac{2z^3}{1-z}\\ \implies & f(z) &= \frac{(1+z)^2}{z}f(z^2) + z^2\left(\frac{1+z}{1-z}\right)\\ \implies & \frac{(1-z)^2}{z} f(z) &= \frac{(1-z^2)^2}{z^2}f(z^2) + z(1-z^2) \end{array} $$ Substitute $z^{2^k}$ for $z$ in last expression and sum over $k$, we obtain
$$f(z) = \frac{z}{(1-z)^2}\sum_{k=0}^\infty \left(z^{2^k} - z^{3\cdot2^k}\right) = \left( \sum_{m=1}^\infty m z^m \right)\sum_{k=0}^\infty \left(z^{2^k} - z^{3\cdot2^k}\right)$$
With this expression, we can read off $T(n)$ as the coefficient of $z^n$ in $f(z)$ and get
$$T(n) = \sum_{k=0}^{\lfloor \log_2 n\rfloor} ( n - 2^k ) - \sum_{k=0}^{\lfloor \log_2(n/3)\rfloor} (n - 3\cdot 2^k)$$
For $n > 2$, we can simplify this as $$\bbox[4pt,border: 1px solid black;]{ T(n) = n \color{red}{\big(\lfloor \log_2 n\rfloor - \lfloor \log_2(n/3)\rfloor\big)} - \color{blue}{\big( 2^{\lfloor \log_2 n\rfloor + 1} - 1 \big)} + 3\color{blue}{\big( 2^{\lfloor \log_2(n/3)\rfloor +1} - 1\big)}}\tag{*2}$$
There are several observations we can make.
When $n = 2^k, k > 1$, we have $$T(n) = n(k - (k-2)) - (2^{k+1} - 1) + 3(2^{k-1} - 1) = \frac32 n - 2$$
When $n = 3\cdot 2^{k-1}, k > 0$, we have $$T(n) = n(k - (k-1)) - (2^{k+1} - 1) + 3(2^k - 1) = \frac53 n - 2$$
For $2^k < n < 3\cdot 2^{k-1}, k > 1$, the coefficient for $n$ in $(*2)$ (i.e the factor in red color) is $2$, while the rest (i.e those in blue color) didn't change with $k$. So $T(n)$ is linear there with slope $2$.
- For $3\cdot 2^{k-1} < n < 2^{k+1}, k > 1$, the coefficient for $n$ in $(*2)$ is now 1. Once gain $T(n)$ is linear there but with slope $1$ instead.
Combine these, we find in general
$$\frac32 n - 2 \le T(n) \le \frac53 n - 2 \quad\text{ for }\quad n > 2$$ and $T(n) = O(n)$ as expected. However, $\frac{T(n)}{n}$ doesn't converge to any number but oscillate "between" $\frac32$ and $\frac53$.
Above is a picture ilustrating the behavior of $T(n)$. The blue pluses are the value of $T(n) - (\frac32 n - 2)$ computed for various $n$. The red line is $\frac{n}{6} = (\frac53 n - 2) - (\frac32 n - 2)$. As one can see, $T(n)$ doesn't converge to any straight line. Instead, it oscillate between lines $\frac32 n - 2$ and $\frac53 n - 2$ as discussed before.
Hint:
$$f(3)=2f(2)-1=3,\\f(4)=2f(2)-1=3,\\f(5)=2f(3)-1=5,\\f(6)=2f(3)-1=5,\\f(7)=2f(4)-1=5,\\f(8)=2f(4)-1=5,\\f(9)=2f(5)-1=9,\\f(10)=2f(5)-1=9,\\f(11)=2f(6)-1=9,\\f(12)=2f(6)-1=9,\\\cdots$$
and a pattern emerges. To make it even more obvious, consider $g(n):=f(n)-1$, and
$$g(3)=2g(2)=2^1,\\g(4)=2g(2)=2^1,\\g(5)=2g(3)=2^2,\\g(6)=2g(3)=2^2,\\g(7)=2g(4)=2^2,\\g(8)=2g(4)=2^2,\\\cdots$$
Best Answer
Note there is no general method to deal with recurrence relations involving the ceiling function. It depends on things like how the ceiling function is being used, what the initial value is, etc. To handle them, I suggest you calculate a few values to see if there's any pattern you can determine, and then try to prove it.
For example, consider the equation you gave of
$$a_n=0.2*\lceil a_{n-1} \rceil \tag{1}\label{1}$$
You didn't specify an initial value, so I will show the behavior of various ranges. First, if $-1 \lt a_0 \le 0$, then $a_1 = 0.2 \times \lceil a_0 \rceil = 0.2 \times 0 = 0$. Thus, you get $0 = a_2 = a_3 = \ldots$, i.e., $a_n = 0$ for all $n \ge 0$. Note having $a_1 = 20$ is not consistent with using $a_0 = 0$ and the recurrence relation for the rest of the values. However, if you do start from $a_1 = 20$ instead, then you get $a_2 = 4$, $a_3 = 0.8$, then $0.2 = a_4 = a_5 = \ldots$, i.e., $a_n = 0.2$ for $n \ge 4$.
Next, if $0 \lt a_0 \le 1$, then you have $a_1 = 0.2 \times \lceil a_0 \rceil = 0.2 \times 1 = 0.2$. However, then $a_3 = 0.2$ as well and, in fact, $a_n = 0.2$ for all $n \ge 1$.
However, if $1 \lt a_0 \le 2$, then $a_1 = 0.2 \times \lceil a_0 \rceil = 0.2 \times 2 = 0.4$. Once again, you then get $0.2 = a_2 = a_3 \ldots$, so $a_n = 0.2$ for all $n \ge 2$.
In fact, for any positive $a_0$, you'll eventually get all later values of $a_n$ to be $0.2$, and for any $a_0$ being non-positive, you'll eventually get all later values to be $0$.