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?

Improve this question
$\endgroup$
16
  • $\begingroup$ Ugh. Would you settle for something like $B(n)\approx n/4$? $\endgroup$
    – Rick Decker
    Oct 17, 2018 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$
    – John L.
    Oct 17, 2018 at 18:09
  • $\begingroup$ why is it 8 and not 16? $\endgroup$
    – dreamin
    Oct 17, 2018 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$
    – John L.
    Oct 17, 2018 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$
    – John L.
    Oct 17, 2018 at 18:16

2 Answers 2

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
1
  • $\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, 2018 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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