Fruits of procrastination

Month: October, 2014

October 21, 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}.

1 Comment
October 4, 2014

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.

7 Comments