Number Theory Revise part 1

I thought to revise David Burton and try out some problems which I didn't do. It's been almost 2 years since I touched that book so let's see!

Also, this set of problems/notes is quite weird since it's actually a memory lane. You will get to know on your own! I started with proving a problem, remembered another problem and then another and so on! It was quite fun cause all these questions were the ones I really wanted to solve!

And this is part1 or else the post would be too long.

Problem1: Prove that for $n\ge 1$ 

$$\binom{n}{r}<\binom{n}{r+1}$$ iff $0\le r\le \frac{n-1}{2}$

Proof: We show that $\binom{n}{r}<\binom{n}{r+1}$ for $0\le r\le \frac{n-1}{2}$ and use the fact that $$\binom{n}{n-r}=\binom{n}{r}$$

Note that $\binom{n}{r}= \frac{n!}{r!(n-r)!}, \binom{n}{r+1}=\frac{n!}{(r+1)!(n-r-1)!}$ 

Comparing, it's enough to show that $$\frac{1}{n-r}<\frac{1}{r+1}\text{ or show } n-r>r+1$$

which is true as $0\le r\le \frac{n-1}{2}$

Problem2: Show that the expressions $\frac{ (2n)!}{n!(n+1)!}$ integers.

Proof: Now, one way of proving this is $$\frac{(2n+1)!}{n!(n+1)!}=\frac{2n+1}{n}\cdot \frac{(2n)!}{(n-1)!(n+1)}=\frac{2n+1}{n}\cdot \binom{2n-1}{n+1}\in \Bbb Z$$

but $\gcd(n,2n+1)=1\implies n|\binom{2n}{n-1}$

---

It's the Catalan numbers formula btw :P

Hmm... I did have another idea..

The other possible way I think is using $v_p.$

Let $p$ be an odd prime dividing $n$ then $$v_p\left(\frac{(2n)!}{(n-1)!(n+1)!}\right)=v_p(2n!)-v_p(n-1!)-v_p(n+1!)$$  

$$=\frac{2n-s_p(2n)-n+1+s_p(n-1)-n-1+s_p(n+1!)}{p-1}=\frac{s_p(n-1)+s_p(n+1)-s_p(2n)}{p-1}$$

where $s_p$ denotes the sum of digits of $n$ is base $p$.

Since $p|n\implies s_p(n+1)=s_p(n)+1.$

And it is well known that $p-1|x-s_p(x).$

Now, to show that $n|\left(\frac{(2n)!}{n!(n+1)!}\right)$ enough to show that $$s_p(n-1)+s_p(n)+1-s_p(2n)\ge v_p(n)\cdot (p-1)$$

When $2|n$ note that $v_2(\frac{(2n)!}{n!(n+1)!})=v_2(\frac{(2n+1)!}{n!(n+1)!})=v_2(\binom{2n+1}{n})$

Talking about Legendre, I should try to prove this identity after a few problems and also try to prove the Catalan numbers identity!

Problem3: Proof that $\frac{(2n)!}{2^n}$ is an integer.

Proof: Note that $v_2(x\cdot (x+1)\cdot (x+2)\cdot (x+3))\ge 3.$

So $$v_2((2n)!)\ge [3\times \frac{2n-2}{4}]\ge n$$

Another proof would be, 

 Consider a set $S$ containing $2$ copies of $n$ distinct elements. Then $S$ has total $2n$ objects.

Then, the total number of permutations of these objects $$=\frac{(2n)!}{(2!)^n}=\frac{(2n)!}{2^n}.$$

Since the number of permutations is an integer, therefore, $\dfrac{(2n)!}{2^n}$ is an integer. 

Actually, this method is also useful when we have to show that $x!y!z!| (x+y+z)!.$ 

Problem 4: Prove that $x_1!x_2!\dots x_n!| (x_1+x_2+\dots+x_n)!$

Proof: Left to the reader :P

Problem5: Prove that $2^n$ does not divide $n!$

Proof: By legendre, $v_p(n!)=n-s(2^n)<n.$

Here are two pretty well known problems which I find pretty hard if induction didn't exists

Problem6: Prove that $\frac{2n!}{n!2^n}$ is an integer.

Proof: We use induction. For $n=1$ it's true.

Suppose it's true for $n=k.$ We will show that it's true for $n=k+1.$

Note that $$\frac{(2k+2)!}{(k+1)!2^{k+1}}=(2k+1)\cdot \frac{(2k+2)}{k+1}\cdot\frac{(2k)!}{(k)!2^{k+1}}=(2k+1)\cdot \frac{(2k)!}{(k)!2^{k}}\in \Bbb Z$$

Problem 7: Prove that $\frac{3n!}{n!6^n}$ is an integer.

Proof: Note that $$2^n|2n!|\frac{3n!}{n!}.$$ So enough to show that $3^n|\frac{3n!}{n!3^n}$ whose proof is similar to the above.

Problem 8: Establish the inequality $2^n<\binom{2n}{n}<2^{2n}.$

Proof: Note that $$\frac{2n!}{n!2^n}\in \Bbb Z^{+}\implies 2^n<\binom{2n}{n}.$$

Also, we have $$\binom{2n}{n}=\dfrac{1\cdot 3\cdot \dots \cdot (2n-1)}{2\cdot 4\cdot \dots 2n}2^{2n}.$$ This simply manipulations.

But note that $$\dfrac{1\cdot 3\cdot \dots \cdot (2n-1)}{2\cdot 4\cdot \dots 2n}\le 1\implies \binom{2n}{n}<2^{2n}.$$  

Problem 9: Prove that sum of the first $n$ triangle numbers is less $2$ that is,

$$\frac{1}{1}+\frac{1}{3}+\dots+\frac{1}{t_n}<2$$

Proof: Note that we just have $$\frac{2}{1\cdot 2}+\frac{2}{2\cdot 3}+\dots+\frac{2}{n(n+1)}=2\cdot {1-\frac{1}{n+1}}<2$$

Problem 10: Fibonacci addition law $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$

Proof: It's simply induction.

We varry $n.$ Say it's true for $n=1,\dots, k.$ We will show that $n=k+1.$

Then $$F_{k+1+m}=F_{k+m}+F_{k-1+m}=F_{k-1}F_m+F_kF_{m+1}+F_{k-2}F_{m}+F_{k-1}F_{m+1}$$  

$$=F_kF_m+F_{k+1}F_{m+1}$$

Okie, now I think the following is a nice problem for the existence of the formula of Fibonacci numbers.

Problem 11: Show that $$\frac{f_{2k+2}} { f_{k+1} } = \frac{f_{2k} } { f_k } + \frac{f_{2k-2} } {f_{k-1} }$$

Proof: Show that $$\frac{f_{2k+2}} { f_{k+1} } = \frac{f_{2k} } { f_k } + \frac{f_{2k-2} } {f_{k-1} }$$

I used the formula for Fibonacci i.e 

$$F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right).$$

Then $$\frac{f_{2k+2}} { f_{k+1} }=\left(\frac{1+\sqrt{5}}{2}\right)^{k+1}+\left(\frac{1-\sqrt{5}}{2}\right)^{k+1}$$

And we get $$\frac{f_{2k}} { f_{k} }=\left(\frac{1+\sqrt{5}}{2}\right)^{k}+\left(\frac{1-\sqrt{5}}{2}\right)^{k}$$

And $$\frac{f_{2k-2}} { f_{k-1} }=\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}+\left(\frac{1-\sqrt{5}}{2}\right)^{k-1}$$

Or show $$\left(\frac{1+\sqrt{5}}{2}\right)^{k+1}+\left(\frac{1-\sqrt{5}}{2}\right)^{k+1}= \left(\frac{1+\sqrt{5}}{2}\right)^{k}+\left(\frac{1-\sqrt{5}}{2}\right)^{k}+\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}+\left(\frac{1-\sqrt{5}}{2}\right)^{k-1}$$

But note that both $\left(\frac{1+\sqrt{5}}{2}\right), \left(\frac{1-\sqrt{5}}{2}\right)$ are roots of $x^2=x+1.$ So $x^{k+1}=x^{k}+x^{k-1}$

So we get  that $$\left(\frac{1+\sqrt{5}}{2}\right)^{k+1}=\left(\frac{1+\sqrt{5}}{2}\right)^{k}+\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}$$

And similarly for $\left(\frac{1-\sqrt{5}}{2}\right).$

Problem 12: Prove by induction on Fibonacci numbers: show that $f_n\mid f_{2n}$

Proof: Note that 

$$\frac{f_{2k+2}} { f_{k+1} } = \frac{f_{2k} } { f_k } + \frac{f_{2k-2} } {f_{k-1} }$$

By induction, we can assume that $\frac{f_{2k} } { f_k }, \frac{f_{2k-2} } {f_{k-1} }$ are integers.

Problem 13: Prove that $$\gcd(F_n,F_m) = F_{\gcd(n,m)}$$

Proof: Using formula for we get that $F_{\gcd(n,m)}|F_n, F_m\implies F_{\gcd(m,n)}|\gcd(F_n,F_m)$

Now $\gcd(n,m)=mx+ny$ for some $x,y$ by bezout. But $F_{\gcd(n,m)}= F_{mx-1}F_{ny}+F_{mx}F_{ny+1}.$

But $$\gcd(F_n,F_m)|F_{mx-1}F_{ny}+F_{mx}F_{ny+1}=F_{\gcd(n,m)}$$

$$\implies \gcd(F_n,F_m) = F_{\gcd(n,m)}.$$

Well, I am still left to prove the legendre formula.

Theorem: $$v_p(n!)=\frac{n-s_p(n)}{p-1}$$

Proof: Let $n=n_lp^l+\dots+n_1p+n_0$ in base $p.$

Then $$\lfloor{\frac{n}{p^i}}\rfloor=n_lp^{l-i}+\dots+n_{i+1}p+n_i.$$

Then $$v_p(n!)=\sum_{i=1}^l \lfloor {\frac{n!}{p^i}} \rfloor =\sum_{i=1}^l n_lp^{l-i}+\dots+n_{i+1}p+n_i.$$

Which is actually, $$n_l\sum_{i=1}^l p^{l-i}+n_{l-1}\sum_{i=1}^l p^{l-i-1}+\dots +n_{i+1}$$

$$=\frac{1}{p-1}\left( n_l\cdot (p^{l}-p)+n_{l-1}\cdot (p^{l-1}-p)+\dots +n_{i+1}\cdot (p-1)\right)$$

$$=\frac{n-s_p(p)}{p-1}$$

See you soon with the next post!

Sunaina💜