How many flips of a fair coin are needed to get at least one run of at least $k$ consecutive heads with probability $\ge1/2$? The following question  was asked today: 

How many flips $n$ of a fair coin are needed to get at least one run of at least $k$ consecutive heads with probability $P_{k,n}\ge1/2$? 

The question was negatively received and deleted by the OP. However, the answer to this question is not quite trivial and has been a subject of several studies. This answer will be given below. 
 A: According to Mathworld (see also Wikipedia), 
$$P_{k,n}=1-\frac{F_{k,n}}{2^n},\tag{1}$$
where, for each natural $k$, $(F_{k,n})_{n=1}^\infty$ is the sequence of $k$-step Fibonacci numbers, defined recursively by the formula 
$$F_{k,n}=\sum_{i=1}^k F_{k,n-i}\tag{2}$$
with the initial conditions $F_{k,n}=0$ for $n\le0$ and $F_{k,1}=F_{k,2}=1$. 
It is known (see e.g. formula (4)) that for $k\ge2$
$$F_{k,n}=R\Big(\frac{(r_k-1) r_k^{n-1}}{(k+1) r_k-2 k}\Big),\tag{3}$$
where $R(x)$ is the nearest integer to a real number $x$, and $r_k$ is the only root $r$ of the equation $r^k(2-r)=1$ in the interval $(1,2)$. 
It follows that for each fixed natural $k\ge2$ we have $F_{k,n}=r_k^{(1+o(1))n}=o(2^n)$ as $n\to\infty$. In view of (1), this implies that the smallest $n$ in question exists and equals 
$$n_k:=\min\{n\colon F_{k,n}\le\tfrac12\,2^n\}.$$ 
The values of $n_2,\dots,n_{10}$, found by Mathematica -- in about 0.1 sec using (2) (storing all the previously found values of $F_{k,n}$), and in about 6 sec using (3) -- are $4, 10, 22, 44, 89, 178, 356, 711, 1421$. Also, obviously, $n_1=1$. 
