A $2^k$ vertices tournament contains a set of at most $k$ vertices that is not dominated Show that a $2^k$ vertices tournament contains a set of at most $k$ vertices that is not dominated. 
A Dominated Set, as it was defined for us, is a set of vertices $S$ in a tournament $T$ such that there is a vertex $v\in T\setminus S$ such that points at all the vertices in $S$. 
I have been trying different things so far, but I believe it is not true. Taking a $2^2$ tournament, one can easily have a $3$ vertices set $S$ which is not dominated. Where have I gone wrong?
 A: I will prove by induction that the statement "every tournament of order $2^k$ contains an undominated set of size $\le k$" is true for all $k\ge1$. (It is false for $k=0$.)
The base case $k=1$ is trivial. For the induction step, consider a tournament $T$ of order $2^{k+1}$. Since the average outdegree in $T$ is $2^k-\frac12$, we can choose a vertex $v$ with outdegree $\ge2^k$ and indegree $\lt2^k$. Thus we can choose a set $V_0\subseteq V(T)\setminus\{v\}$ of size $|V_0|=2^k$ such that every vertex which dominates $\{v\}$ belongs to $V_0$. Applying the induction hypothesis to the subtournament induced by $V_0$, we get a set $X_0\subseteq V_0$ of size $|X_0|\le k$ which is not dominated by any vertex in $V_0$. If we let $X=\{v\}\cup X_0$, then we have $|X|\le k+1$ and $X$ is not dominated by any vertex in $V(T)$.
A better formulation:
Every tournament of order at most $a_k=2^{k+1}-2$ contains an undominated set of size $\le k$.
Here $a_k=2^{k+1}-2$ is the solution of the recurrence $a_{k+1}=2a_k+2$ with initial value $a_0=0$. The proof is essentially the same as before: in a tournament of order $\le a_{k+1}$ we can choose a vertex of indegree $\le a_k$.
