Resolviendo la relación de recurrencia de la forma $T(n)=T \left ( \frac {nb}{a} \right )+T \left ( \frac {(n-b)c}{a} \right )+n$

Question

¿Cómo resolvemos una recurrencia de la forma:

$T(n)=T \biggl ( \dfrac {nb}{a} \biggr )+T \biggl ( \dfrac {(n-b)c}{a} \biggr )+n$ ?

Intenté sustituir $q= \dfrac {a}{b},\ r= \dfrac {a}{c}, \ s= \dfrac {bc}{a}$ para obtener:

$T(n)=T \left ( \dfrac {n}{q} \right )+T \left ( \dfrac {n}{r}-s \right )+n$

pero no podía seguir adelante.

Esta pregunta resuelve un problema algo similar, pero tiene una forma conveniente que permite una sustitución prolija.

Answer 1

Supongamos que $a,b,c \neq0 $ y $ \dfrac {b}{a} \neq1 $ para mantener el significado clave de esta pregunta.

$T(n)=T \biggl ( \dfrac {nb}{a} \biggr )+T \biggl ( \dfrac {(n-b)c}{a} \biggr )+n$

$T(n)-T \biggl ( \dfrac {nb}{a} \biggr )-T \biggl ( \dfrac {(n-b)c}{a} \biggr )=n$

Conseguir la parte de la solución particular es muy fácil cuando $a-b-c \neq0 $ .

Deje que $T_p(n)=An+B$ ,

Luego $An+B- \biggl ( \dfrac {Anb}{a}+B \biggr )- \biggl ( \dfrac {A(n-b)c}{a}+B \biggr ) \equiv n$

$ \dfrac {(a-b-c)An}{a}+ \dfrac {bcA}{a}-B \equiv n$

$ \therefore\begin {cases} \dfrac {(a-b-c)A}{a}=1 \\\dfrac {bcA}{a}-B=0 \end {cases}$

$ \begin {cases}A= \dfrac {a}{a-b-c} \\B = \dfrac {bc}{a-b-c} \end {cases}$

$ \therefore T_p(n)= \dfrac {an+bc}{a-b-c}$

Pero conseguir la parte de la solución particular no es fácil cuando $a-b-c=0$ .

Para obtener la parte de la solución complementaria, debemos manejar la ecuación $T_c(n)-T_c \biggl ( \dfrac {nb}{a} \biggr )-T_c \biggl ( \dfrac {(n-b)c}{a} \biggr )=0$

Incluso dejar $T_c(n)= \int_ {- \infty }^ \infty e^{nt}K(t)~dt$ ,

Luego $ \int_ {- \infty }^ \infty e^{nt}K(t)~dt- \int_ {- \infty }^ \infty e^{ \frac {nbt}{a}}K(t)~dt- \int_ {- \infty }^ \infty e^{ \frac {(n-b)ct}{a}}K(t)~dt=0$

$ \int_ {- \infty }^ \infty e^{nt}K(t)~dt- \int_ {- \infty }^ \infty e^{ \frac {bnt}{a}}K(t)~dt- \int_ {- \infty }^ \infty e^{ \frac {cnt}{a}}e^{- \frac {bct}{a}}K(t)~dt=0$

$ \int_ {- \infty }^ \infty e^{nt}K(t)~dt- \text {sgn} \left ( \dfrac {a}{b} \right ) \int_ {- \infty }^ \infty e^{nt}K \left ( \dfrac {at}{b} \right )d \left ( \dfrac {at}{b} \right )- \text {sgn} \left ( \dfrac {a}{c} \right ) \int_ {- \infty }^ \infty e^{nt}e^{-bt}K \left ( \dfrac {at}{c} \right )d \left ( \dfrac {at}{c} \right )=0$

$ \int_ {- \infty }^ \infty e^{nt}K(t)~dt- \int_ {- \infty }^ \infty\dfrac {a}{b} \text {sgn} \left ( \dfrac {a}{b} \right )e^{nt}K \left ( \dfrac {at}{b} \right )dt- \int_ {- \infty }^ \infty\dfrac {a}{c} \text {sgn} \left ( \dfrac {a}{c} \right )e^{nt}e^{-bt}K \left ( \dfrac {at}{c} \right )dt=0$

$ \int_ {- \infty }^ \infty\left (K(t)- \dfrac {a}{b} \text {sgn} \left ( \dfrac {a}{b} \right )K \left ( \dfrac {at}{b} \right )- \dfrac {a}{c} \text {sgn} \left ( \dfrac {a}{c} \right )e^{-bt}K \left ( \dfrac {at}{c} \right ) \right )e^{nt}~dt=0$

$ \therefore K(t)- \dfrac {a}{b} \text {sgn} \left ( \dfrac {a}{b} \right )K \left ( \dfrac {at}{b} \right )- \dfrac {a}{c} \text {sgn} \left ( \dfrac {a}{c} \right )e^{-bt}K \left ( \dfrac {at}{c} \right )=0$

Pero aún así es muy difícil de resolver en general.