# How to transform a differential equation to easier one using change of variables?

I am currently studying analysis of Algorithms and have come across a paper about Median of 3 partition for quick select. The authors have solved the recurrence using the generating functions and came up to a partial differential equation (eq 6 in the paper):

$$\frac{1}{6} \frac{\partial^2Q}{\partial z^2} - \left [ \frac{1}{(1-z)^2} + \frac{u^2}{(1-uz)^2} \right]Q = \frac{u}{(1-u)} \left [ \frac{1}{(1-z)^4} - \frac{u^3}{(1-uz)^4} \right].$$

Expressing $Q(z,u)$ as (eq 7 in paper)

$$Q(z,u) = \frac{1}{(1-z)^2(1-uz)^2}E(z,u)$$

and substitute $z = 1+t(1-u)/u$.

$$G(t,u)=E\left(1+\frac{1-u}{u}t,u\right),$$

(eq 8 in paper) the original equation will transforms to:

$$t(1-t)\frac{\partial^2 G}{\partial t^2} + (-4+8t)\frac{\partial G}{\partial t} - 8G = 6(1-u)\frac{u(1-t)^4 - t^4}{t(1-t)}$$

(eq 9 in paper). Now, I am not able to understand how the authors get this equation because when I tried to solve using the same substitutions I get the below one:

$$t^2\frac{\partial^2 G}{\partial t^2} - 8t\frac{\partial G}{\partial t} + 2G \left [ 10 + \frac{u^2}{(1-u)^2} \right] = 6u^2t^2.$$

Are the both equations same or am I doing some mistake?

-
It seems you already know this and corrected it in your reproduction, but for others who look at the paper it might be helpful to know that there's a typo in equation (8) and $\mathcal Q$ on the left-hand side should be $\mathcal G$. (I also corrected a typo in your version of equation (8).) – joriki Jul 20 '12 at 5:54
@joriki: That typo is not easy to spot. Good eyes! – user26872 Jul 20 '12 at 7:47
Corrected one more typo on last equation.. – Anuj Jul 20 '12 at 8:35

It looks like you are missing some terms. I give a few partial results that should allow you to track them down. $$\begin{eqnarray*} \frac{d}{dz} &=& \frac{dt}{dz} \frac{d}{dt} \\ &=& \frac{1}{dz/dt} \frac{d}{dt} \\ &=& \frac{u}{1-u} \frac{d}{dt} \\ \frac{d}{dz} Q(z) &\rightarrow& \frac{u}{1-u} \frac{d}{dt} \left(\frac{u^2}{(1-u)^4} \frac{1}{t^2(1-t)^2} G(t) \right) \\ &=& \frac{u^3}{(1-u)^5} \frac{1}{t^3(1-t)^3} [(t(1-t)G'(t) - 2(1-2t)G(t)] \hspace{5ex} \clubsuit \\ \frac{d^2}{dz^2} Q(z) &\rightarrow& \frac{u}{1-u} \frac{d}{dt} \left(\clubsuit\right) \end{eqnarray*}$$

-
Got it. I was confused why I am not getting that $(1-t)$ term and now realized i did this mistake. Thanks for pointing it out. – Anuj Jul 20 '12 at 9:16
@Anuj: You're welcome. Glad to help. – user26872 Jul 20 '12 at 15:16