Intereting Posts

Generalization of variance to random vectors
Matrices with real entries such that $(I -(AB-BA))^{n}=0$
Isomorphic quotients by isomorphic normal subgroups
A short proof for $\dim(R)=\dim(R)+1$?
Binomial Distribution Problem – Airline Overbooking
Find a $4\times 4$ matrix $A$ where $A\neq I$ and $A^2 \neq I$, but $A^3 = I$.
$y'=$ ${-x+\sqrt{(x^2+4y)}}\over 2$ , $y(2)=-1$
How to prove there are no solutions to $a^2 – 223 b^2 = -3$.
Difference between Euclidean Space and $\mathbb{R}^n$ other than origin?
Right-continuity of completed filtration
Modulo of sum of random variables
What are the conditions for a polygon to be tessellated?
What are zero divisors used for?
Fixed Point of $x_{n+1}=i^{x_n}$
A finite field cannot be an ordered field.

$f(0) = 3$

$f(1) = 3$

$f(n) = f(\lfloor n/2\rfloor)+f(\lfloor n/4\rfloor)+cn$

- Bounding the modified Bessel function of the first kind
- Order of the smallest group containing all groups of order $n$ as subgroups.
- Can a function “grow too fast” to be real analytic?
- Compactly supported function whose Fourier transform decays exponentially?
- Summing $\frac{1}{a}-\frac{1}{a^4}+\frac{1}{a^9}-\cdots$
- Help understanding the complexity of my algorithm (summation)

Intuitively it feels like O(n), meaning somewhat linear with steeper slope than c, but I have forgot enough math to not be able to prove it…

- Solving Recurrence equation
- Meaning of “polynomially larger”
- What are the rules for equals signs with big-O and little-o?
- Exponential growth of cow populations in Minecraft
- Recursive square root problem
- How to find $\lim a_n$ if $ a_{n+1}=a_n+\frac{a_n-1}{n^2-1} $ for every $n\ge2$
- Big O notation sum rule
- Solve the reccurence $a_n= 4a_{n−1} − 2 a_{n−2}$
- Series about Euler-Maclaurin formula
- Let $x_n$ be the (unique) root of $\Delta f_n(x)=0$. Then $\Delta x_n\to 1$

In your recurrence, set $n=4m$ for an integer $m$. Then $f(4m) = f(2m)+f(m) + 4 c m$. From your original equation, it’s easy to determine $f(1) = 3$, $f(2) = 6 + 2c$, $f(4) = 9 + 6 c$.

Now, let $g(n) = f(2^n)$, so the equation translates into $g(n+2) = g(n+1) + g(n) + c 2^{n+2}$. The solution to this equation is easy to find.

$$

g(n) = c_1 F_n + c_2 L_n + c 2^{n+2}

$$

where $F_n$ are Fibonacci numbers, and $L_n$ are Lucas numbers. Asymptotically, Fibonacci and Lucas numbers grow only as $\phi^n$, and since $\phi < 2$, the dominating term is $c 2^{n+2}$.

Rolling back, $f(m) \sim 4 c m + o(m)$.

Suppose we first study $$g(n) = f(n)-3$$ which has $g(0)=g(1)=0$ and

$$g(n) = g(\lfloor n/2 \rfloor) + g(\lfloor n/4 \rfloor) + cn+3.$$

Then it is not difficult to see that for the binary representation of $n$ being

$$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$

we have that for $n\ge 2,$

$$g(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor-1}

[z^j] \frac{1}{1-z-z^2}

\left(3 + c\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}\right)$$

which in turn implies

$$f(n) = 3 + \sum_{j=0}^{\lfloor \log_2 n \rfloor-1}

[z^j] \frac{1}{1-z-z^2}

\left(3 + c\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}\right).$$

Now note that the polynomial term is the generating function of the Fibonacci numbers shifted down by one, so that this simplifies to an attractive **exact** formula for **all** $n$ which is

$$f(n) = 3 + \sum_{j=0}^{\lfloor \log_2 n \rfloor-1}

F_{j+1}

\left(3 + c\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}\right)

= 3 F_{\lfloor \log_2 n \rfloor+2} +

c \sum_{j=0}^{\lfloor \log_2 n \rfloor-1}

F_{j+1} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}.$$

Next we compute upper and lower bounds. For an upper bound consider a string of one digits, which gives the following bound which is actually attained and cannot be improved upon:

$$f(n) \le 3 F_{\lfloor \log_2 n \rfloor+2} +

c \sum_{j=0}^{\lfloor \log_2 n \rfloor-1}

F_{j+1} \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^{k-j}

\\ = 3 F_{\lfloor \log_2 n \rfloor+2} +

c \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} (2^{\lfloor \log_2 n \rfloor+1-j}-1)

\\= c + (3-c) F_{\lfloor \log_2 n \rfloor+2} +

c 2^{\lfloor \log_2 n \rfloor+1} \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{-j}.$$

Now the sum term converges to a limit. We have

$$ \sum_{j=0}^\infty F_{j+1} 2^{-j}

= \frac{1}{\sqrt{5}}

\left(\varphi \sum_{j=0}^\infty (\varphi/2)^j

– (-1/\varphi) \sum_{j=0}^\infty (-1/\varphi/2)^j\right)

\\ = \frac{1}{\sqrt{5}}

\left(\frac{\varphi}{1-\varphi/2}+\frac{1/\varphi}{1+1/\varphi/2}\right) =4.$$

For a lower bound consider a one followed by a string of zeros, giving

$$f(n) \ge 3 F_{\lfloor \log_2 n \rfloor+2} +

c \sum_{j=0}^{\lfloor \log_2 n \rfloor-1}

F_{j+1} 2^{\lfloor \log_2 n \rfloor-j}

=3 F_{\lfloor \log_2 n \rfloor+2} +

c 2^{\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor-1}

F_{j+1} 2^{-j}. $$

The sum term converges to four as before. We see that the dominant asymptotics in both bounds come from the two terms

$$F_{\lfloor \log_2 n \rfloor+2} \quad\text{and}\quad 2^{\lfloor \log_2 n \rfloor}.$$

Note that

$$F_n \sim \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n$$

which means that the power of two dominates, giving a final complexity of

$$\Theta\left(2^{\lfloor \log_2 n \rfloor}\right)

= \Theta\left(2^{\log_2 n}\right) = \Theta(n).$$

This MSE link points to a similar calculation.

- Are all of the following statements equivalent? (vectors and matrices)
- What is duality?
- The adjoint of finite rank operator is finite rank
- Why is the volume of a cone one third of the volume of a cylinder?
- Idempotent matrix is diagonalizable?
- An open subset of a manifold is a manifold
- Sufficient conditions for separately measurable functions being jointly measurable.
- Minimal polynomial of $\alpha^2$ given the minimal polynomial of $\alpha$
- Additive quotient group $\mathbb{Q}/\mathbb{Z}$ is isomorphic to the multiplicative group of roots of unity
- If $a$ and $b$ are integers such that $9$ divides $a^2 + ab + b^2$ then $3$ divides both $a$ and $b$.
- Operator: not closable!
- Jacobian of exponential mapping in SO3/SE3
- How to prove this series problem: $\sum_{r=1}^\infty \frac{(r+1)^2}{r!}=5e-1$?
- Find all integral solutions to $a+b+c=abc$.
- Examples of functions where $f(ab)=f(a)+f(b)$