$n$ bugs moving in a line

Fun question!

Your calculation for the first three expectations is correct, but your guessed formula is not. Here is one possible approach. It will point you to some cool online resources along the way.

Let me call the expected number you are after $e(n)$. Let $B$ be the big fat guy who will eat everybody in front of him. Then the probability that $B$ is in any given place in the sequence is $1/n$, and if he is in place $i$, then the number of survivors is himself plus whatever happens behind him, which is just a question about permutations of the remaining $i-1$ bugs. Thus, you get the recursive formula $$ e(n) = \frac{1}{n}\sum_{i=0}^{n-1}(1+e(i)) = 1+ \frac{1}{n}\sum_{i=1}^{n-1}e(i). $$

Edit: See lulu's and Christian Blatter's answers for the solution to this recursion! You can easily prove that that's the solution using the series identity between harmonic numbers $$ \sum_{k=1}^n H_k = (n+1)(H_{n+1}-1). $$

Here is MAGMA code, which you can paste in the online calculator to compute this sequence:

function prob(n)
if n lt 2 then return n; end if;
return 1/n*&+[1+prob(i): i in [0..n-1]];
end function;

Now you can say

[prob(i): i in [1..10]];

and get the sequence

$$ 1, 3/2, 11/6, 25/12, 137/60, 49/20, 363/140, 761/280, 7129/2520, 7381/2520,... $$ If you multiply this by $n!$, you get an integer sequence:

$$ 1, 3, 11, 50, 274, 1764, 13068, 109584, 1026576, 10628640,... $$ The encyclopedia of integer sequences recognises this as sequence A000254, and gives several interpretations for it. For example it is the total number of cycles in all permutations of $\{1,\ldots,n\}$, and you can easily prove (exercise!) that that's what it should be for your puzzle.

To use Linearity:

(assume no two ants have the same size)

Let $X_i$ be the indicator variable for the $i^{th}$ ant. Thus $X_i=1$ if the $i^{th}$ ant survives this process, and $X_i=0$ otherwise.

Since the largest of the first $i$ ants is equally likely to be in any of those $i$ slots we see that $$E[X_i]=\frac 1i$$

It follows that the answer is $$E=E\left[ \sum X_i\right]=\sum E[X_i]=\sum_{i=1}^n\frac 1{i}$$

Thus the answer is just the $n^{th}$ Harmonic Number.

Denote by $E(n)$ the expected number of surviving ants. If the smallest ant is the last in the line it will survive. If not it will certainly be eaten and have no effect on the number of surviving ants. It follows that $$E(n)={1\over n}\bigl(1+E(n-1)\bigr)+{n-1\over n}E(n-1)={1\over n}+E(n-1)\ .$$ This leads to $$E(n)=H(n):=\sum_{k=1}^n{1\over k}\ .$$