The problem:
For any $n\in\mathbb{N}$ define:
$$v_{n,0}=\frac{1}{n},$$
$$v_{n,k}=\frac{k+1}{k+n}(2v_{n,k-1}+1),\;\;\forall k\in\mathbb{N}.$$
Prove that $v_{n,n}\rightarrow\infty$ as $n\rightarrow\infty$.
Prove that $\liminf_{n\rightarrow\infty}\frac{v_{n,n}}{\sqrt{n}}>0$.
Prove that $v_{n,cn}\rightarrow\frac{c}{1-c}$ as $n\rightarrow\infty$, for any constant $c<1$.
$\hspace{32pt}$(this is where I am stuck, there are no my attempts at this)
The background problem:
The object of interest is
$$d(n,k)=\frac{\#\text{connected bipartite graphs with }n\text{ vertices and }k\text{ edges}}{\#\text{connected}\phantom{ bipartite\ \ }\text{graphs with }n\text{ vertices and }k\text{ edges}}.$$
For which I want to prove that $d(n,cn)\rightarrow 0$ when $n\rightarrow\infty$ for any $c\geq 2$ (as suggested by a computer calculation). My approach was elementary...
My background work:
I have started by fixing $n$ and writing down some inequalities for these numbers with different $k$'s:
$$\begin{align}\text{Let}\;\;\;a_k=\#\text{connected non-bipartite graphs with }n\text{ vertices and }k\text{ edges} ,&\text{ and}\\\text{Let}\;\;\;b_k=\#\text{connected}\phantom{nona}\text{bipartite graphs with }n\text{ vertices and }k\text{ edges,}\end{align}$$
with an intention to bound $a_{cn}/b_{cn}$ from below by some function which is increasing with $n$. Let's observe:
- To add an edge to a graph counted by $a_{k-1}$ we have exactly $\binom{n}{2}-k+1$ ways to go, and we'll end up with a graph counted by $a_k$.
- To add an edge to a graph counted by $b_{k-1}$ we have exactly $\binom{n}{2}-k+1$ ways to go. At least $\frac{n(n-2)}{4}$ of these ways lead to a graph counted by $a_k$, while (equivalently) at most $\frac{n^2}{4}-k+1$ of these ways lead to a graph counted by $b_k$.
- To remove an edge from a graph counted by either $a_k$ or $b_k$ we have between $k-n+1$ and $k$ ways to go, and if the graph was counted by $b_k$ then we end up with a graph counted by $b_{k-1}$.
By counting all the ways we can get to a graph counted by $a_k$ and to a graph counted by $b_k$ from $a_{k-1}$ and $b_{k-1}$ and accounting for multiple ways to get to the same graph, we arrive at the next inequalities:
$$a_k\geq\frac{a_{k-1}\left(\binom{n}{2}-k+1\right)+b_{k-1}\frac{n(n-2)}{4}}{k},$$
$$b_k\leq\frac{b_{k-1}\left(\frac{n^2}{4}-k+1\right)}{k-n+1}.$$
The transition:
We can combine this with $u_k:=a_k/b_k$ to get:
$$u_k\geq\frac{k-n+1}{k}\cdot\frac{u_{k-1}\left(\binom{n}{2}-k+1\right)+\frac{n(n-2)}{4}}{\frac{n^2}{4}-k+1}.$$
We also know that $a_{n-1}=0$ because every connected graph with $n-1$ edges and $n$ vertices is a tree, therefore bipartite and counted by $b_{n-1}$, while $b_{n-1}$ is non-zero (it doesn't matter what it's equal to). This also gives $u_{n-1}=0$. The conjecture is equivalent to that $u_{2n}\rightarrow\infty$ when $n\rightarrow\infty$. Now, calculating the $u_k$ is easy computationally and it gives that $u_{2n}$ is roughly $\sqrt{n}$. Another interesting result is that $u_{cn}$ seems to converge to $\frac{c-1}{2-c}$ for any $1\leq c<2$. Can someone help me prove this asymptotic?
The final simplification:
It is a matter of elementary inequalities that
$$u_k\geq\frac{k-n+1}{k}(2u_{k-1}+1).$$
Computer suggests the same behavior for this recursion too. Now we should also simplify the indices with the introduction of $v_k:=u_{n+k}$:
$$v_k\geq\frac{k+1}{k+n}(2v_{k-1}+1),\hspace{24pt}\text{with }\;\;v_0=\frac{1}{n}.$$
Now we ought to prove that $v_n\rightarrow\infty$ as $n\rightarrow\infty$. The convergent result is that $v_{cn}\rightarrow\frac{c}{1-c}$ as $n\rightarrow\infty$ for any $c<1$.