4 out of 5 dentists recommend this WordPress.com site

## Month: October, 2014

### A new method for determining the limits of recursion relations

This is meant as a note. I will definitely expand this article later.

I hope this method has not been discovered before :(.

Say $x_n=f(x_{n-1})$ is a recursion relation. Then $\lim\limits_{n\to\infty} x_n$ is the intersection point of $y=f(x)$ and $x=f(y)$.

For example, if we have $x_n=\sqrt{5 x_{n-1}+6}$, then $\lim\limits_{n\to\infty} x_n$ is the y-coordinate of the intersection of $y=\sqrt{5x+6}$ and $x=\sqrt{6y+5}$.

### Original, constructive proof of Hilbert’s Basis Theorem.

Edit: After reading proofs of this theorem, it seems to me that this is similar in spirit to an already established proof (Proof 2 on ProofWiki, for instance).

This is a constructive proof of Hilbert’s Basis Theorem.

Hilbert’s Basis Theorem says that if $R$ is a Noetherian ring (every ideal has a finite number of generators), then so is the polynomial ring $R[x]$.

Let $I\subset R[x]$ be an ideal. It contains polynomials and constants. Let us take the set of all leading coefficients of the polynomials in $I$, and call it $S$. This is clearly an ideal! Hence, $S=(s_1,s_2,\dots,s_n)$. There are polynomials of the form $s_1x^{k_1}+\dots, s_2x^{k_2}+\dots,s_nx^{k_n}+\dots$ in $I$.

Let $i$ be $\sup\{k_1,k_2,\dots,k_n\}$.

Now take the set $A=\{0,1,2,\dots i\}$. The **leading coefficients** of polynomials of degree $j$ for each $j\in A$, $\cup \{0\}$, form an ideal. Hence, there must be a finite number of generators for the ideal containing leading coefficients of polynomials of degree $j$.

For example, take all polynomials of degree $1$ in $I$. The leading coefficients of such polynomials $\cup\{0\}$ form an ideal (try adding these polynomials or multiplying them with elements from $R$). As $R$ is Noetherian, the ideal of leading coefficients has a finite number of generators- say $\{a_1,a_2,\dots,a_t\}$. It follows that $(a_1x+c_1),(a_2x+c_2),\dots,(a_tx+c_t)$ belong to this ideal of polynomials of degree $1$, and can generate the leading coefficient of **any** polynomial of degree $1$ in $I$.

Proceeding by recursion, we will soon have the finite list of generators generating the leading coefficients of all polynomials of degree $\leq i$. We can hence say that we have the list of polynomials that can be linearly added to generate all polynomials of degree $\leq i$. This is not difficult to see. It is important to note that we can also linearly generate the polynomials with leading coefficients $\{s_1,s_2,\dots,s_t\}$.

Important note on notation: let $a_{1j},a_{2j},\dots,a_{t_jj}$ be the finite number of coefficients which generate the leading coefficients of all polynomials of degree $j$ belonging to $I$.

It is easy to see that $\text{Coeff}=\{a_{10},\dots,a_{t_00};a_{11}\dots,a_{t_1,1};\dots,a_{1i},\dots,a_{t_ii}\}$ generates the whole of $I$. For polynomials of degree $\leq i$, we’ve already shown how. For polynomials of degree $\geq i+1$, generate all leading coefficients using $\{s_1,s_2,\dots,s_n\}$ (which in turn are generated by $\text{Coeff}$), and then generate the rest using $\text{Coeff}$ right away.