1
$\begingroup$

I was trying to solve the recurrence relation in order to get a some big-O bound $$ B(n) = B(n-4) + \frac{1}{n} + \frac{5}{n^{2} + 6} + \frac{7n^{2}}{3n^{3} + 8}$$ by following the accepted answer here. I expanded which resulted in $$ B(n) = B(n-8) + \frac{1}{n-1} + \frac{5}{(n-1)^{2} + 6} + \frac{7(n-1)^{2}}{3(n-1)^{3} + 8} + \frac{1}{n} + \frac{5}{n^{2} + 6} + \frac{7n^{2}}{3n^{3} + 8}$$

This lead to $$ B(n) = B(n-4k) + \frac{1}{n-k} + \frac{5}{(n-k)^{2} + 6} + \frac{7(n-k)^{2}}{3(n-k)^{3} + 8} + \frac{1}{n-k} + \frac{5}{(n-k)^{2} + 6} + \frac{7(n-k)^{2}}{3(n-k)^{3} + 8}$$ However, I get stuck when replacing $k$ with $n$ since this results in dividing by zero. How do I proceed? Can it solved by the iteration?

$\endgroup$
  • $\begingroup$ Ugh. Would you settle for something like $B(n)\approx n/4$? $\endgroup$ – Rick Decker Oct 17 '18 at 17:22
  • $\begingroup$ The first calculation is wrong. It should be $B(n) = B(n-8) + \frac{1}{n-4} + \frac{5}{(n-4)^{2} + 6} + \frac{7(n-4)^{2}}{3(n-4)^{3} + 8} + \frac{1}{n} + \frac{5}{n^{2} + 6} + \frac{7n^{2}}{3n^{3} + 8}$ $\endgroup$ – Apass.Jack Oct 17 '18 at 18:09
  • $\begingroup$ why is it 8 and not 16? $\endgroup$ – dreamin Oct 17 '18 at 18:10
  • $\begingroup$ Welcome to Computer Science! Your question looks nice. If this problem comes from an online source such as a programming contest or coding camp, please provide a URL. If it comes from a textbook or a paper, a reference. If it comes from some real task in your life, some background? All those information motivate and help people answer the question faster and better. Please add those information in the question since people and search engine are not expected of looking at comments. $\endgroup$ – Apass.Jack Oct 17 '18 at 18:13
  • $\begingroup$ Can you replace n by (n-4) everywhere in $B(n) = B(n-4) + \frac{1}{n} + \frac{5}{n^{2} + 6} + \frac{7n^{2}}{3n^{3} + 8}$? The only place that can be simplified is $(n-4)-4=n-8$. $\endgroup$ – Apass.Jack Oct 17 '18 at 18:16
1
$\begingroup$

We can rewrite your recursion as $$ B(n) = B(n-4) + \Theta\left(\frac{1}{n}\right). $$ It follows that $$ \begin{align*} B(n) &= \Theta\left(\frac{1}{n} + \frac{1}{n-4} + \frac{1}{n-8} + \cdots\right) \\ &= \Theta\left(\frac{1}{n/4} + \frac{1}{n/4-1} + \frac{1}{n/4-2} + \cdots \right) \\ &= \Theta(\log (n/4)) = \Theta(\log n), \end{align*} $$ using the formula for the sum of a harmonic series.

$\endgroup$
0
$\begingroup$

The base case will depend on $n$, but I will assume that $B(0)$, $B(1)$, $B(2)$, and $B(3)$ are known. I used the Wolfram Cloud to crunch some stuff. The following summarizes the 'simplified' results when $n=4k,\,4k+1,\,4k+2,\,\text{and}\,4k+3$ (these are given in Mathematica input form for later use in the Wolfram Cloud, etc):

B[n_]=Piecewise[{{(144*EulerGamma - (60*I)*Sqrt[6]*PolyGamma[0, (-I/2)*Sqrt[3/2]] + (60*I)*Sqrt[6]*PolyGamma[0, (I/2)*Sqrt[3/2]] + (60*I)*Sqrt[6]*PolyGamma[0, (-I/4)*(Sqrt[6] - I*n)] -
(60*I)*Sqrt[6]*PolyGamma[0, (I/4)*(Sqrt[6] + I*n)] + 144*PolyGamma[0, 1 + n/4] + 112*n^2*RootSum[8 + 3*n^3 - 36*n^2*#1 + 144*n*#1^2 - 192*#1^3 & , PolyGamma[0, -#1]/(n^2 - 8*n*#1 +
16*#1^2) & ] - 896*n*RootSum[-184 + 144*n - 36*n^2 + 3*n^3 - 576*#1 + 288*n*#1 - 36*n^2*#1 - 576*#1^2 + 144*n*#1^2 - 192*#1^3 & , (PolyGamma[0, -#1] + PolyGamma[0, -#1]*#1)/(16
- 8*n + n^2 + 32*#1 - 8*n*#1 + 16*#1^2) & ] + 1792*RootSum[-184 + 144*n - 36*n^2 + 3*n^3 - 576*#1 + 288*n*#1 - 36*n^2*#1 - 576*#1^2 + 144*n*#1^2 - 192*#1^3 & , (PolyGamma[0,
-#1] + 2*PolyGamma[0, -#1]*#1 + PolyGamma[0, -#1]*#1^2)/(16 - 8*n + n^2 + 32*#1 - 8*n*#1 + 16*#1^2) & ] - 7*n^2*RootSum[-1 + 24*#1^3 & , PolyGamma[0, -#1]/#1^2 & ] +
14*n*RootSum[-1 + 24*#1^3 & , (n*PolyGamma[0, -#1] + 4*PolyGamma[0, -#1]*#1)/#1^2 & ] - 7*RootSum[-1 + 24*#1^3 & , (n^2*PolyGamma[0, -#1] + 8*n*PolyGamma[0, -#1]*#1 +
16*PolyGamma[0, -#1]*#1^2)/#1^2 & ])/576, Mod[n, 4] == 0}, {((-15*I)*Sqrt[6]*PolyGamma[0, (-I/4)*(-3*I + Sqrt[6])] + (15*I)*Sqrt[6]*PolyGamma[0, (I/4)*(3*I + Sqrt[6])] +
(15*I)*Sqrt[6]*PolyGamma[0, (-I/4)*(Sqrt[6] - I*n)] - (15*I)*Sqrt[6]*PolyGamma[0, (I/4)*(Sqrt[6] + I*n)] + 28*n^2*RootSum[8 + 3*n^3 - 36*n^2*#1 + 144*n*#1^2 - 192*#1^3 & , PolyGamma[0,
-#1]/(n^2 - 8*n*#1 + 16*#1^2) & ] - 224*n*RootSum[-184 + 144*n - 36*n^2 + 3*n^3 - 576*#1 + 288*n*#1 - 36*n^2*#1 - 576*#1^2 + 144*n*#1^2 - 192*#1^3 & , (PolyGamma[0, -#1] +
PolyGamma[0, -#1]*#1)/(16 - 8*n + n^2 + 32*#1 - 8*n*#1 + 16*#1^2) & ] + 448*RootSum[-184 + 144*n - 36*n^2 + 3*n^3 - 576*#1 + 288*n*#1 - 36*n^2*#1 - 576*#1^2 + 144*n*#1^2 -
192*#1^3 & , (PolyGamma[0, -#1] + 2*PolyGamma[0, -#1]*#1 + PolyGamma[0, -#1]*#1^2)/(16 - 8*n + n^2 + 32*#1 - 8*n*#1 + 16*#1^2) & ] - 28*n^2*RootSum[-89 + 324*#1 - 432*#1^2 +
192*#1^3 & , PolyGamma[0, -#1]/(9 - 24*#1 + 16*#1^2) & ] + 56*n*RootSum[-89 + 324*#1 - 432*#1^2 + 192*#1^3 & , (-3*PolyGamma[0, -#1] + n*PolyGamma[0, -#1] + 4*PolyGamma[0,
-#1]*#1)/(9 - 24*#1 + 16*#1^2) & ] - 28*RootSum[-89 + 324*#1 - 432*#1^2 + 192*#1^3 & , (9*PolyGamma[0, -#1] - 6*n*PolyGamma[0, -#1] + n^2*PolyGamma[0, -#1] - 24*PolyGamma[0,
-#1]*#1 + 8*n*PolyGamma[0, -#1]*#1 + 16*PolyGamma[0, -#1]*#1^2)/(9 - 24*#1 + 16*#1^2) & ] + 144*DifferenceRoot[Function[{y, n}, {(4*n - n)*y[n] + 2*(-2 - 4*n + n)*y[1 + n] + (4 + 4*n
- n)*y[2 + n] == 0, y[0] == 0, y[1] == n^(-1)}]][(-3 + n)/4])/144, Mod[n, 4] > 2}, {((-15*I)*Sqrt[6]*PolyGamma[0, (-I/4)*(-I + Sqrt[6])] + (15*I)*Sqrt[6]*PolyGamma[0, (I/4)*(I + Sqrt[6])] +
(15*I)*Sqrt[6]*PolyGamma[0, (-I/4)*(Sqrt[6] - I*n)] - (15*I)*Sqrt[6]*PolyGamma[0, (I/4)*(Sqrt[6] + I*n)] + 28*n^2*RootSum[8 + 3*n^3 - 36*n^2*#1 + 144*n*#1^2 - 192*#1^3 & , PolyGamma[0,
-#1]/(n^2 - 8*n*#1 + 16*#1^2) & ] - 224*n*RootSum[-184 + 144*n - 36*n^2 + 3*n^3 - 576*#1 + 288*n*#1 - 36*n^2*#1 - 576*#1^2 + 144*n*#1^2 - 192*#1^3 & , (PolyGamma[0, -#1] +
PolyGamma[0, -#1]*#1)/(16 - 8*n + n^2 + 32*#1 - 8*n*#1 + 16*#1^2) & ] + 448*RootSum[-184 + 144*n - 36*n^2 + 3*n^3 - 576*#1 + 288*n*#1 - 36*n^2*#1 - 576*#1^2 + 144*n*#1^2 -
192*#1^3 & , (PolyGamma[0, -#1] + 2*PolyGamma[0, -#1]*#1 + PolyGamma[0, -#1]*#1^2)/(16 - 8*n + n^2 + 32*#1 - 8*n*#1 + 16*#1^2) & ] - 28*n^2*RootSum[-11 + 36*#1 - 144*#1^2 +
192*#1^3 & , PolyGamma[0, -#1]/(1 - 8*#1 + 16*#1^2) & ] + 56*n*RootSum[-11 + 36*#1 - 144*#1^2 + 192*#1^3 & , (-PolyGamma[0, -#1] + n*PolyGamma[0, -#1] + 4*PolyGamma[0,
-#1]*#1)/(1 - 8*#1 + 16*#1^2) & ] - 28*RootSum[-11 + 36*#1 - 144*#1^2 + 192*#1^3 & , (PolyGamma[0, -#1] - 2*n*PolyGamma[0, -#1] + n^2*PolyGamma[0, -#1] - 8*PolyGamma[0, -#1]*#1
+ 8*n*PolyGamma[0, -#1]*#1 + 16*PolyGamma[0, -#1]*#1^2)/(1 - 8*#1 + 16*#1^2) & ] + 144*DifferenceRoot[Function[{y, n}, {(4*n - n)*y[n] + 2*(-2 - 4*n + n)*y[1 + n] + (4 + 4*n - n)*y[2
+ n] == 0, y[0] == 0, y[1] == n^(-1)}]][(-1 + n)/4])/144, Mod[n, 4] == 1}}, ((-15*I)*Sqrt[6]*PolyGamma[0, (-I/4)*(-2*I + Sqrt[6])] + (15*I)*Sqrt[6]*PolyGamma[0, (I/4)*(2*I + Sqrt[6])] +
(15*I)*Sqrt[6]*PolyGamma[0, (-I/4)*(Sqrt[6] - I*n)] - (15*I)*Sqrt[6]*PolyGamma[0, (I/4)*(Sqrt[6] + I*n)] + 28*n^2*RootSum[8 + 3*n^3 - 36*n^2*#1 + 144*n*#1^2 - 192*#1^3 & , PolyGamma[0,
-#1]/(n^2 - 8*n*#1 + 16*#1^2) & ] - 224*n*RootSum[-184 + 144*n - 36*n^2 + 3*n^3 - 576*#1 + 288*n*#1 - 36*n^2*#1 - 576*#1^2 + 144*n*#1^2 - 192*#1^3 & , (PolyGamma[0, -#1] +
PolyGamma[0, -#1]*#1)/(16 - 8*n + n^2 + 32*#1 - 8*n*#1 + 16*#1^2) & ] + 448*RootSum[-184 + 144*n - 36*n^2 + 3*n^3 - 576*#1 + 288*n*#1 - 36*n^2*#1 - 576*#1^2 + 144*n*#1^2 -
192*#1^3 & , (PolyGamma[0, -#1] + 2*PolyGamma[0, -#1]*#1 + PolyGamma[0, -#1]*#1^2)/(16 - 8*n + n^2 + 32*#1 - 8*n*#1 + 16*#1^2) & ] - 7*n^2*RootSum[-2 + 9*#1 - 18*#1^2 + 12*#1^3 &
, PolyGamma[0, -#1]/(1 - 4*#1 + 4*#1^2) & ] + 14*n*RootSum[-2 + 9*#1 - 18*#1^2 + 12*#1^3 & , (-2*PolyGamma[0, -#1] + n*PolyGamma[0, -#1] + 4*PolyGamma[0, -#1]*#1)/(1 - 4*#1 +
4*#1^2) & ] - 7*RootSum[-2 + 9*#1 - 18*#1^2 + 12*#1^3 & , (4*PolyGamma[0, -#1] - 4*n*PolyGamma[0, -#1] + n^2*PolyGamma[0, -#1] - 16*PolyGamma[0, -#1]*#1 + 8*n*PolyGamma[0, -#1]*#1
+ 16*PolyGamma[0, -#1]*#1^2)/(1 - 4*#1 + 4*#1^2) & ] + 144*DifferenceRoot[Function[{y, n}, {(4*n - n)*y[n] + (-4 - 8*n + 2*n)*y[1 + n] + (4 + 4*n - n)*y[2 + n] == 0, y[0] == 0, y[1] ==
n^(-1)}]][(-2 + n)/4])/144]

This line assigns a function B[n_] in Mathematica which gives $B(n)$ given $n$, using the best explicit formula I could get, which was still really ugly.

$\endgroup$
  • $\begingroup$ I'm not sure I was clear in what I was trying to do and also how this relates to the question so I provided more clarity to the post. $\endgroup$ – dreamin Oct 18 '18 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.