# Big-O Solving Recurrence Relation by iteration with fractions

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?

• Ugh. Would you settle for something like $B(n)\approx n/4$? Commented Oct 17, 2018 at 17:22
• 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}$ Commented Oct 17, 2018 at 18:09
• why is it 8 and not 16? Commented Oct 17, 2018 at 18:10
• 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. Commented Oct 17, 2018 at 18:13
• 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$. Commented Oct 17, 2018 at 18:16

## 2 Answers

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.

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.

• 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. Commented Oct 18, 2018 at 2:52