Online Help

Solves divide and conquer recurrences, meaning those of the form $Af\left(R^{n}k\right)+Bf\left(R^{m}k\right)=0$, where R is either numeric or a name, m and n are integers, and where A and B are independent of k.

See the help page for LREtools[REcreate] for the definition of the format of a problem.

$\mathrm{with}\left(\mathrm{LREtools}\right)\:$

$\mathrm{prob}≔\mathrm{REcreate}\left(\left\{y\left(nk\right)=2y\left(k\right)\right\}\,y\left(k\right)\,\varnothing \right)$

$\mathrm{prob}≔\mathrm{RESol}\left(\left\{y\left(nk\right)-2y\left(k\right)=0\right\}\,\left\{y\left(k\right)\right\}\,\varnothing \,\mathrm{INFO}\right)$

$\mathrm{divconq}\left(\mathrm{prob}\right)$

$y\left(1\right)k^{\frac{\ln \left(2\right)}{\ln \left(\mathrm{n~}\right)}}$

$\mathrm{divconq}\left(f\left(r^{3}k\right)=2f\left(r^{2}k\right)\,f\left(k\right)\,\varnothing \right)$

$f\left(1\right)k^{\frac{\ln \left(2\right)}{\ln \left(r\right)}}$