Solving a recurrence relation using Z transform
The calculation of the $Z$ transform above is not correct. For example, the equation $$ Z[T(n)n]=\frac{Z[T(n)]}{z^{n}} $$ is not correct. Instead, you have $$ Z[T(n)n] = Z[T(n)]  Z[n] = Z[T(n)]  \frac{z}{(1z)^2} $$ which, when substituted into $$Z[T(n)]=Z[T(n)n]+\frac{z}{(z1)^{2}}$$ results in the trivial $$ Z[T(n)]=Z[T(n)]. $$ To obtain a nontrivial equation for $Z[T(n)]$, you have to first express the $Z$ transforms of $T(\lfloor n/4 \rfloor)$ and $T(\lfloor 3n/4 \rfloor)$ in terms of the $Z$ transform of $T(n)$ (taking $T(n)$ here to be an arbitrary sequence), and then use the recurrence to express $Z[T(n)]$ in terms of the $Z$ transforms of $T(\lfloor n/4 \rfloor)$ and $T(\lfloor 3n/4 \rfloor)$, also taking into account the initial values $T(1)=T(2)=T(3)=1$. Although it is possible to do this, the expressions that result are rather complex, so it would be difficult to solve this problem directly using the $Z$ transform.
Using a result of S. Roura ("An improved master theorem for divideandconquer recurrences", S. Roura, 1997) it is possible to show that $$ T(n)\sim C_0 n \ln n, \qquad \text{where } C_0=(\frac 14 \ln \frac 14+\frac 34 \ln \frac 34)^{1} \approx 1.77829895. $$ Also, a generalized form of the recurrence for $T(n)$ is analyzed by Drmota and Szpankowski in "A master theorem for discrete divide and conquer recurrences", 2011. Their Theorem 2.1 also shows in this case that $T(n)\sim Cn\ln n$ for some constant $C$.
For $C_0$ as above, it is straightforward to show by induction that $T(n)\le C_0 n\ln n$ for all $n\ge 2$. This can be checked directly for $2\le n\le 7$. Then, if $n\ge8$, \begin{eqnarray*} T(n)&=&T(\lfloor \frac n4 \rfloor)+T(\lfloor \frac{3n}4\rfloor)+n\\ &\le& C_0 (\lfloor \frac n4 \rfloor \ln \lfloor \frac {n}4 \rfloor)+ C_0 (\lfloor \frac{3n}4 \rfloor \ln \lfloor \frac {3n}4 \rfloor)+ n,\\ &\ & \qquad \qquad \text{by the induction hypothesis}\\ &\le& C_0 (\frac n4 \ln \frac {n}4 )+C_0(\frac {3n}4 \ln \frac{3n}4) + n\\ &=& C_0 (\frac n4 \ln n + \frac {3n}4 \ln n + \frac n4 \ln \frac 14 + \frac {3n}4 \ln \frac 34) + n\\ &=& C_0 n \ln n + C_0 ( \frac 14 \ln \frac 14 + \frac {3}4 \ln \frac 34)n + n\\ &=& C_0 n \ln n, \end{eqnarray*} completing the induction.
Related videos on Youtube
user1489886
Updated on August 01, 2022Comments

user1489886 over 1 year
I'm trying to solve the following recurrence using Z transforms:
For $n\in \mathbb{N}^{*}$
$T(n)=1\ for\ n< 4$
$T(n)=T(\lfloor \frac{n}{4} \rfloor)+T(\lfloor \frac{3n}{4} \rfloor)+n\ for\ n\geq 4$
I should find an expression for T(n).
Using $Z[T(n)](z)$ as the Z transform for T(n) (or more simply, just $Z[T(n)]$), I have arrived to the following solution attempt:
$Z[T(n)]=Z[T(\lfloor \frac{n}{4} \rfloor)]+Z[T(\lfloor \frac{3n}{4} \rfloor)]+\frac{z}{(z1)^{2}}$
Using the property of linearity of any Z transformation we can add the arguments of the first two terms of the right side and get the following:
$Z[T(n)]=Z[T(\frac{n}{4})+T(\frac{3n}{4})]+\frac{z}{(z1)^{2}}$
or
$Z[T(n)]=Z[T(n)n]+\frac{z}{(z1)^{2}}$
I guess that the first term of the right side of the equation is just $Z[T(n)]$ shifted to the right with n units, and so it can be written as follows:
$Z[T(n)n]=\frac{Z[T(n)]}{z^{n}}$
Therefore, the equation becomes
$Z[T(n)]=\frac{Z[T(n)]}{z^{n}}+\frac{z}{(z1)^{2}}$
By subtracting from both sides of the equation the first term of the right side we get:
$Z[T(n)]\cdot \frac{z^{n}1}{z^{n}}=\frac{z}{(z1)^{2}}$
and therefore
$Z[T(n)]=\frac{z^{n+1}}{(z1)^{2}\cdot (z^{n}1)}$
Now the problem is that it is very difficult for me to reverse transform this (I don't even know how to find a value for the convergence radius). I have a strong feeling that I was wrong somewhere along the way, so I would like to know if there is a better way to do this using Z transforms.
And if there is not the case, can anybody please explain to me if Z transforms can be used at all to solve this equation?
And if not, can anybody please tell me if there is a way to calculate an upper bound for T(n) (which is reasonably low)?

user1489886 over 10 yearsWhen I was thought the Z transform they told me I could use it to solve any constant coefficient recurrence and I wanted to get its money's worth. Thanks for the useful answer. That induction provided a nice approach.