How to prove that two univariate polynomials are always algebraically dependent? How to prove that two univariate polynomials(over any field) are always algebraically dependent? Also, how to prove the generalization of this question i.e if number of polynomials are more than number of variables then those polynomials are always algebraically dependent? I know one proof, but still posting this question because I want to know about alternative proofs of this nice fact.
The proof I know is this:

If those n+1 polynomials are independent then they will form a transcendence base of $k(x_1,..x_n)/k$ and it's dimension will be $n+1.$ but $\{x_1,...x_n\}$ is a transcendence basis for $k(x_1,..x_n)/k$ and its dimension is $n.$ But dimension of two transcendence bases should be same. So contradiction.

My guess is this elementary fact can be proved by many different ways.
 A: I think there's also a more explicit symmetry-based/computational approach (compared to Michael Stoll's linear algebra approach). EDIT 12/13/14: "computational" was the wrong choice of word.
For the $n=1$ (univariate) case this is a problem from (Michael) Artin's Algebra previously discussed on MSE here. Given $f,g\in k[T]$, we want a polynomial $P\in k[X,Y]$ such that $P(a,b) = 0$ (here $a,b\in \overline{k}$ are any points in the (infinite) algebraic closure of $k$) if and only if there exists $t\in \overline{k}$ such that $f(t) - a = g(t) - b = 0$. This latter condition is, by the "product of differences of roots" definition of the resultant (which for fixed $a,b$ has $k[a,b]$-coefficients by the fundamental theorem of symmetric polynomials), equivalent to the (formal) vanishing of the resultant of $f(T) - X$ and $g(T) - Y$, which is a polynomial in $k[X,Y]$.
If I'm not mistaken, this should generalize via the multivariate resultant: see Wikipedia or this paper ("Explicit formulas for the multivariate resultant" by Carlos D'Andrea and Alicia Dickenstein).
[BTW, I believe that at least in the univariate case, combining the above with another exercise in Artin shows that if $k = \overline{k}$ is algebraically closed and $f,g$ are not both constant, then (0) the ideal of working polynomials $P$ is principal, and if $m$ is a generator (unique up to scaling), then (1) $m$ is irreducible in $k[X,Y]$; (2) for $(a,b)\in k^2$, we have $m(a,b) = 0$ iff there exists $t\in k$ with $(x(t),y(t)) = (a,b)$; and (3) the resultant is (up to scaling) a power of $m$.
(0,1) can be proven by standard means (e.g. Bezout's identity in the PID $k(Y)[X]$; I'm told this is really a dimension theory argument)---one might only need that $k$ is infinite, not algebraically closed---and (2,3) by looking at the resultant ($k = \overline{k}$ is important here). I don't think Hilbert's nullstellensatz is necessary.]
A: Here is an elementary proof for the case of univariate polynomials.
Let $f, g \in F[x]$, where $F$ is your field, with $\deg(f) = m$, $\deg(g) = n$.
Then $f^k g^l$ has degree $km + ln$. For $0 \le k \le N/(2m)$, $0 \le l \le N/(2n)$,
this degree is $\le N$. So there are $\ge N^2/(4mn)$ expressions $f^k g^l$
of degree $\le N$, and they live in an $F$-vector space of dimension $N+1$.
If $N$ is sufficiently large, then the number of elements you get in this space
is larger than its dimension,
so they must be linearly dependent. This gives you an algebraic relation
between $f$ and $g$.
This generalizes to polynomials in arbitrarily many variables.
A: For polynomials over the field of complex numbers $\mathbb{C}$ there is yet another method. Namely, polynomials  in $m$ variables with coefficients over $\mathbb{C}$ can be considered as meromorphic functions on the complex projective space $\mathbb{CP}^m$.  To prove  algebraic dependence of $k$ polynomials with  $k > m$ (as a trivial corollary) one can use the following (non-trivial) theorem due to C. L. Siegel and W. Thimm: Let $X$ be a compact connected complex manifold.  The  functions $f_1,...,f_k$  meromorphic on $X$ are algebraically dependent if and only if they are analytically dependent (i.e., $df_1(x)\wedge...\wedge f_k(x)=0$ at every point $x \in X$ where all $f_1,...f_k$ are holomorphic). 
The proof of the Siegel-Thimm theorem can be found e.g. in ``Holomorphic Morse Inequalities and Bergman Kernels" by Xiaonan Ma and George Marinescu, Birkh\"auser, Basel 2007 (Theorem 2.2.9). 
