Expected value for linear scan before encountering one of k elements You are given a random permutation of $n$ distinct elements labeled $[0..n-1]$.
If you go through them one at a time what's the expected number of items you'll
have to go through before you encounter the element labeled 0?
This is a basic derivation:
$E[X] = \sum_{i=0}^{n-1} i \cdot P(\text{i failures followed by success})$
$=\sum_{i=1}^{n-1} i \cdot \underbrace{
\frac{n-1}{n}\cdot 
\frac{n-2}{n-1}\cdots  
\frac{n-i+1}{n-i+2}\cdot
\frac{n-i}{n-i+1}}_{i \text{ failed trials}}\cdot
\underbrace{\frac{1}{n-i}}_{success}$
$=\sum_{i=1}^{n-1} i \cdot \frac{1}{n} $
$=\frac{1}{n}(n-1)\frac{1+(n-1)}{2}$ 
$= \frac{n-1}{2}$
I got curious about how this behaves if instead of one element we stop when encountering
either one of 2 given elements, or generally one of $k<=n$ elements. Do we halve the expected value with each additional element?
The k=2 case was not difficult using the formula for sum of squares, yielding: $\frac{n-2}{3}$. Which clearly suggests an induction hypothesis for arbitrary k of: $\frac{n-k}{k+1}$.
Computer simulation supports this result and I was able to compute the sum with a CAS:
$E[X] =\sum_{i=1}^{n-k}i\frac{k(n-i-1)\cdots(n-k-i+1)}{n(n-1)\cdots(n-k+1)} = \frac{n-k}{k+1} $
Which felt reassuring but dishonest. For given n and k the sum can be computed 
by prodigious use of Faulhaber's formula, and sufficient effort. 
I'm interested in a simpler way to do the sum for the general case,
proof by induction and/or an intuitive explanation that's convincing.

Since choosing any of the $k$ given elements stops the process and that final element is not counted, you have to consider the distribution of the other $n-k$ elements.
Imagine a full permutation of the $n$ elements. Each of the $n-k$ other elements can be ain any of $k+1$ gaps: before the first given element, between two given elements, or after the last given element.  The probability of the other element being any particular one of these gaps is $\frac{1}{k+1}$.  So the probability of it being before the first given element is also $\frac{1}{k+1}$.  So the expected number of other elements before the first given element is $\frac{n-k}{k+1}$ as you conjectured.
