Even and odd solutions to time independent Schrodinger equation on symmetric potential I have to solve the following problem:

Consider the potential well: $$ V(x)=-V_0, \hspace{10px} |x|<a/2 $$
  and $0$ everywhere else. $a$ is also a positive constant and so is
  $V_0$. Find the wave function everywhere for an energy $0>E>-V_0$. Also determine the equation that gives the bound states. Verify that there is always at least 1 bound state in the well. 

And I have done that, it is simply solving the time independent Schrodinger equation:
$$
\frac{\hbar^2}{2m}\frac{d^2\psi}{dx^2}+V(x)\psi=E\psi
$$
and afterwards apply continuity of the wave function as well as its derivative. After all that work I get to the following equations:
$$
k\tan\left(\frac{ka}{2}\right)=\tilde{k}, \tag{1}
$$
$$
\frac{1}{k}\tan\left(\frac{ka}{2}\right)=-\frac{1}{\tilde{k}}, 
 \tag{2}
$$
where $k^2=\frac{2m|E|}{\hbar^2}$ and $\tilde{k}^2=\frac{2m}{\hbar^2}(V_0-|E|)$. But these equations can't be both simultaneously true. In fact if the first is true, then without any loss of generality we will have only even solutions, whereas if the second is true then it only admits odd solutions. However, for proving that there is always at least one bound state, I defined:
$$
\chi=\frac{ka}{2} \\
\eta=\frac{\tilde{k}a}{2}
$$
and so if $(1)$ is true then we get:
$$
\chi^2+\eta^2=\frac{mV_0a^2}{2\hbar^2} \\
\chi \tan(\chi)=\eta
$$
which is a system of equations that is always satisfied for any $V_0>0$. On the other hand if we do the same admitting $(2)$ true:
$$
\chi \cot (\chi)=-\eta \\
\chi^2+\eta^2=\frac{mV_0a^2}{2\hbar^2}
$$
which is only satisfied for a certain $V_{0_{min}}$. 
Now here's my question:
I have seen that when the potential is symmetric there can be even and odd solutions to the same equation. But I thought that these solutions were independent and each would give me a different set of solutions, $\psi_n$ such that the general solution would consist of linear combinations of those particular functions but could describe the same wave function. In other words, I thought that in a way the even and odd solutions would simply be different basis for the same quantum system. Again in another way, in fourier analysis, any periodic signal can be decomposed as a sum of complex exponentials, so that was, in a way, my pilar to my understanding, even though we had two different sets of coefficients the end result could still be the same. But based on this result, how could one basis (even) allow any $V_0$ and secure bound states, but on another basis (odd) that does not hold? Shouldn't they describe the same reality?
Also, the potential is just a shifted version of a assymmetric potential which will not give even and odd solutions, but is essentially the same problem only with a shifted reference frame. How can we obtain these two different results?
PS: I have seen other questions on this stackexchange but none answered my doubts.
 A: The even and odd solutions together form the basis. 
Think of Fourier analysis. 
Decompose a generic function on $[-\pi,\pi]$. 
It will consist of a sum of even and odd functions. 
It is only if the function itself is even that it will be composed only of even basis functions and vice versa. 
Addendum 1
$\def\j{\psi}
\def\in{\mathrm{in}}
\def\out{\mathrm{out}}
\def\kt{\tilde k}
\def\J{\Psi}$Note: Your definition of the $k$s is not consistent with your later work. 
Implicitly you are using 
$\kt = \sqrt{-2mE/\hbar^2}$ and 
$k = \sqrt{2m(E+V_0)/\hbar^2}$ under the assumption that 
$-V_0\le E\le 0$. 
Let 
\begin{align*}
\j_\in(x) &= A\cos k x+B\sin k x\\
\j_\out(x) &= C e^{\kt x}+D e^{-\kt x}.
\end{align*}
In deriving 
\begin{align*}
k\tan ka/2&=\kt\tag{1}
\end{align*}
you have assumed that $A\ne 0$. 
Likewise, in deriving
\begin{align*}
(1/k)\tan ka/2=-1/\kt\tag{2}
\end{align*}
you have assumed that $B\ne 0$. 
If these equations could both hold true we must have 
$k^2 = -\kt^2$, which is not possible for a bound state. 
This implies that if (1) holds, that $B=0$ (the solutions are even) and that if (2) holds, that $A=0$ (the solutions are odd). 
Thus, the solutions will consist of even and odd functions, the even satisfying (1) and the odd satisfying (2). 
As you found, for any $V_0>0$ there will always be at least one even solution but there may not be any more solutions.
The even and odd bases are not different bases for the same quantum system. 
The even basis is the basis for even $\j$ and the odd basis is the basis for odd $\j$.
But generically $\j$ is neither even nor odd. 
It will be a linear combination of even and odd basis functions! 
Addendum 2
When we solve the time-dependent Schrodinger equation by separation of variables,  $\J(x,t)\rightarrow\j(x)T(t)$, energy is the constant of separation.
After finding the eigenfunctions $\j_n(x)$ to the resulting time-independent Schrodinger equation (whose eigenvalues are the energies $E_n$) a generic solution to the time-dependent Schrodinger equation will be of the form $\J(x,t)=\sum_n c_n \j_n(x)T_n(t)$.
By applying the initial conditions we can find the $c_n$s, which in general will give us a solution which is a sum over even and odd $\j_n$s with different energies.
A: We should be careful about the meaning 'even and odd solutions form a basis'. Since our Hamiltonian has symmetry under $x \rightarrow -x$, every eigenstate should be also an eigenstate of that symmetry operation.
Therefore, your eigenstates should be either even or odd under $x \rightarrow -x$, but not both. 
Edit: After seeing some surprising comments below my answer, I feel I need to elaborate a little more.  


*

*It is true that even and odd basis are NOT simply two different bases of the same vector space, such as $\{\vec{i},\vec{j}\}$ and $\frac{1}{\sqrt{2}}\{\vec{i}+\vec{j}, \vec{i}-\vec{j}\}$ for $\mathbb{R}^2$.  

*It is indeed a 'mathematically' true statement that ANY function can be decomposed into a linear combination of even and odd functions, if we choose those basis as a complete set and the word 'ANY' assumes some good mathematical conditions. Simplest choice is $\cos$ and $\sin$ functions, as you also know well in the Fourier decomposition. It does not even have to be a combination of even+odd function. Just choosing a complete set is sufficient, and there are many other such complete sets other than $\cos$ and $\sin$.
(2-1). Therefore, above statement does not give you any information about what are the eigenstates. It's not even a quantum mechanical statement, but just a mathematical fact. Given a function, then you can decompose. Function need not be an eigenfunction to be decomposed. Of course, eigenfunction can also be decomposed, since eigenfunction is a function. No Hamiltonian, no eigenstate, no symmetry play the role in this statement. 

*Now, let's move on to your problem. Problem is asking you to find the eigenstates of the given Hamiltonian. To answer your question first, the energy eigenvalue $E$s for your symmetric(eq(1)) and anti-symmetric(eq(2)) calculation are different. So it's very natural that those two equations cannot be satisfied simultaneously. Meaning of this is very clear. Symmetric and anti-symmetric eigenstates have different energies. Keep in mind that your goal is to find $E$, the energy eigenvalue. Since you use different wavefunction for (1) and (2), i.e. different eigenstate, there's no need that the solution($E$) should be the same.  

*Next, we need to answer this question. Are all the energy eigenstates also eigenstates of the symmetry operator (let's say it $P:x\rightarrow -x$, and p comes from parity)? In other words, are all the energy eigenstates even or odd function of $x$?
Assume first for specific eigenvalue $E$, there is only one corresponding eigenstate $|\psi\rangle$ (up to phase factor).  This is the meaning when we say such eigenspace is one dimensional. Then we know for sure that such eigenstate is also an eigenstate of $P$. Proof is in the comment below.
Now, suppose we linear combine even and odd eigenstates in certain way, say $\psi=a\psi_1+b\psi_2$, where $|a|^2+|b|^2=1$ and $P\psi_1=\psi_1, P\psi_2=-\psi_2$. Can this be an energy eigenstate? Certainly not. Because due to the assumption, if $H\psi_1=E_1\psi_1, H\psi_2=E_2\psi_2$, $E_1\neq E_2$ because we know for sure $\psi_1 \neq \psi_2$(function cannot be even and odd simultaneously!). So mixture of even and odd eigenstate cannot be an eigenstate. All energy eigenstates must also be eigenstates of $P$.    

*Finally, we should question if the above assumption is valid. Answer is YES for one dimensional problem. If you have two different $\psi_1(x)$ and $\psi_2(x)$ with the same eigenvalue $E$, plug in those functions into Schrodinger equation $-\frac{\hbar^2}{2m}\frac{d^2 \psi_{1,2}(x)}{dx^2}+V(x)\psi_{1,2}(x)=E\psi_{1,2}(x)$,  multiply $\psi_{2,1}$ for each and subtract to cancel out $V(x),E$ term, and massage the result. You will easily find that $\psi_1$ should be a constant multiple of $\psi_2$. So, in 1d, the assumption holds. It is often told that when we have symmetry in the Hamiltonian, eigenstates can be chosen so they are also an eigenstate of symmetry operator. We just saw that in 1d, stronger statement holds. 

*Unfortunately, in higher dimension, the above assumption is not always true. It's possible that a single eigenvalue corresponds to multiple eigenstates(i.e. degeneracy). This is quite common. Then, we can linearly combine those eigenstates with different symmetry eigenvalues(say, even and odd), and the result still remains as an energy eigenstate(since they all corresponds to the same energy eigenvalue). In such cases, eigenstates need not be an eigenstate of symmetry operator.   

*Time dependence is totally irrelevant to this problem. I don't know why the other answer try to add time in this problem. 

