Skip to main content

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💜
Labels:

Comments

  1. Amit January 23, 2022 at 11:48 AM

    Problem 6 without induction:
    $$\frac{2n!}{n!2^n}$$
    $$=\frac{2n\times 2(n-1)\times .....\times 4\times ×2×(product of the odd terms)}{n!2^n}$$
    $$=\frac{2^n\times n!\times product of odd terms}{n!2^n}$$
    Similar approach can be taken towards Problem 7

    ReplyDelete
    Replies
    1. Nirjhar NathJanuary 23, 2022 at 12:55 PM

      Yeah, it was easy without induction too. For Problem 7, we break 3n! to get 3^n.n! (from 3i terms) along with products of the form (3i-1) and (3i-2). Then the 2's out of (3i-1) and (3i-2) will equal 2^n, for n both even and odd.

      Delete
    2. Sunaina Pati January 25, 2022 at 10:55 AM

      all the problems are easy :P

      Delete
    3. Sunaina Pati January 26, 2022 at 7:19 PM

      Yep I think both work! Thanks for sharing!

      Delete
  2. Abdul AhlawatJanuary 26, 2022 at 2:33 PM

    You might want to recheck your problem statement for P2 :wayaw:

    ReplyDelete
  3. Abdul AhlawatJanuary 26, 2022 at 2:51 PM

    Really nice blog though! IMOSL N8 series when? :prayge:

    ReplyDelete

Post a Comment

Popular posts from this blog

Problems with meeting people!

Yeah, I did some problems and here are a few of them! I hope you guys try them! Putnam, 2018 B3 Find all positive integers $n < 10^{100}$ for which simultaneously $n$ divides $2^n$, $n-1$ divides $2^n - 1$, and $n-2$ divides $2^n - 2$. Proof We have $$n|2^n\implies n=2^a\implies 2^a-1|2^n-1\implies a|n\implies a=2^b$$ $$\implies 2^{2^b}-2|2^{2^a}-2\implies 2^b-1|2^a-1\implies b|a\implies b=2^c.$$ Then simply bounding. USAMO 1987 Determine all solutions in non-zero integers $a$ and $b$ of the equation $$(a^2+b)(a+b^2) = (a-b)^3.$$ Proof We get $$ 2b^2+(a^2-3a)b+(a+3a^2)=0\implies b = \frac{3a-a^2\pm\sqrt{a^4-6a^3-15a^2-8a}}{4}$$ $$\implies a^4-6a^3-15a^2-8a=a(a-8)(a+1)^2\text{ a perfect square}$$ $$\implies a(a-8)=k^2\implies a^2-8a-k^2=0\implies \implies a=\frac{8\pm\sqrt{64+4k^2}}{2}=4\pm\sqrt{16+k^2}. $$ $$ 16+k^2=m^2\implies (m-k)(m+k)=16.$$ Now just bash. USAMO 1988 Suppose that the set $\{1,2,\cdots, 1998\}$ has been partitioned into disjoint pairs $\{a_i,b_i\}$ ($1...
3 comments
Read more

Solving Random ISLs And Sharygin Solutions! And INMO happened!!

Some of the ISLs I did before INMO :P  [2005 G3]:  Let $ABCD$ be a parallelogram. A variable line $g$ through the vertex $A$ intersects the rays $BC$ and $DC$ at the points $X$ and $Y$, respectively. Let $K$ and $L$ be the $A$-excenters of the triangles $ABX$ and $ADY$. Show that the angle $\measuredangle KCL$ is independent of the line $g$ Solution: Note that $$\Delta LDK \sim \Delta XBK$$ and $$\Delta ADY\sim \Delta XCY.$$ So we have $$\frac{BK}{DY}=\frac{XK}{LY}$$ and $$\frac{DY}{CY}=\frac{AD}{XC}=\frac{AY}{XY}.$$ Hence $$\frac{BK}{CY}=\frac{AD}{XC}\times \frac{XK}{LY}\implies \frac{BK}{BC}=\frac{CY}{XC}\times \frac{XK}{LY}=\frac{AB}{BC}\times \frac{XK}{LY} $$ $$\frac{AB}{LY}\times \frac{XK}{BK}=\frac{AB}{LY}\times \frac{LY}{DY}=\frac{AB}{DL}$$ $$\implies \Delta CBK\sim \Delta LDK$$ And we are done. We get that $$\angle KCL=360-(\angle ACB+\angle DKC+\angle BCK)=\angle DAB/2 +180-\angle DAB=180-\angle DAB/2$$ Motivation: I took a hint on this. I had other angles but I did...
4 comments
Read more

How to prepare for RMO?

"Let's wait for this exam to get over".. *Proceeds to wait for 2 whole fricking years!  I always wanted to write a book recommendation list, because I have been asked so many times! But then I was always like "Let's wait for this exam to get over" and so on. Why? You see it's pretty embarrassing to write a "How to prepare for RMO/INMO" post and then proceed to "fail" i.e not qualifying.  Okay okay, you might be thinking, "Sunaina you qualified like in 10th grade itself, you will obviously qualify in 11th and 12th grade." No. It's not that easy. Plus you are talking to a very underconfident girl. I have always underestimated myself. And I think that's the worst thing one can do itself. Am I confident about myself now? Definitely not but I am learning not to self-depreciate myself little by little. Okay, I shall write more about it in the next post describing my experience in 3 different camps and 1 program.  So, I got...
7 comments
Read more

My experiences at EGMO, IMOTC and PROMYS experience

Yes, I know. This post should have been posted like 2 months ago. Okay okay, sorry. But yeah, I was just waiting for everything to be over and I was lazy. ( sorry ) You know, the transitioning period from high school to college is very weird. I will join CMI( Chennai Mathematical  Institue) for bsc maths and cs degree. And I am very scared. Like very very scared. No, not about making new friends and all. I don't care about that part because I know a decent amount of CMI people already.  What I am scared of is whether I will be able to handle the coursework and get good grades T_T Anyways, here's my EGMO PDC, EGMO, IMOTC and PROMYS experience. Yes, a lot of stuff. My EGMO experience is a lot and I wrote a lot of details, IMOTC and PROMYS is just a few paras. Oh to those, who don't know me or are reading for the first time. I am Sunaina Pati. I was IND2 at EGMO 2023 which was held in Slovenia. I was also invited to the IMOTC or International Mathematical Olympiad Training Cam...
11 comments
Read more

IMO Shortlist 2021 C1

 I am planning to do at least one ISL every day so that I do not lose my Olympiad touch (and also they are fun to think about!). Today, I tried the 2021 IMO shortlist C1.  (2021 ISL C1) Let $S$ be an infinite set of positive integers, such that there exist four pairwise distinct $a,b,c,d \in S$ with $\gcd(a,b) \neq \gcd(c,d)$. Prove that there exist three pairwise distinct $x,y,z \in S$ such that $\gcd(x,y)=\gcd(y,z) \neq \gcd(z,x)$. Suppose not. Then any $3$ elements $x,y,z\in S$ will be $(x,y)=(y,z)=(x,z)$ or $(x,y)\ne (y,z)\ne (x,z)$. There exists an infinite set $T$ such that $\forall x,y\in T,(x,y)=d,$ where $d$ is constant. Fix a random element $a$. Note that $(x,a)|a$. So $(x,a)\le a$.Since there are infinite elements and finite many possibilities for the gcd (atmost $a$). So $\exists$ set $T$ which is infinite such that $\forall b_1,b_2\in T$ $$(a,b_1)=(a,b_2)=d.$$ Note that if $(b_1,b_2)\ne d$ then we get a contradiction as we get a set satisfying the proble...
1 comment
Read more

Symmetric Polynomials #week 6

Well... I haven't seen much symmetric polynomials in Olympiads, but still I am learning, because I found them cute. And I am basically using this blog as my notes :P What are symmetric polynomials?  One can understand this with  examples. If we are considering over 3 variables, $x_1,x_2,x_3$ then  $$\sum_{sym}x_1^2\cdot x_2^3\cdot x_3=x_1^2\cdot x_2^3\cdot x_3+x_1^2\cdot x_3^3\cdot x_2+x_2^2\cdot x_1^3\cdot x_3+x_2^2\cdot x_3^3\cdot x_1+x_3^2\cdot x_1^3\cdot x_2.$$ See? $3!$ terms! Let's take one more example with again over 3 variables, $x_1,x_2,x_3$ then $$\sum_{sym}x_1^2\cdot x_2^2= x_1^2\cdot x_2^2+x_1^2\cdot x_3^2+x_2^2\cdot x_1^2+x_2^2\cdot x_3^2+x_3^2\cdot x_1^2+x_3^2\cdot x_2^2$$ Wait.. why 2 times ? So basically what happens in symmetrictric sums, is we go through all $n!$ possible permutations. So, here we have $a^2\cdot b^2\cdot c^0$ as like the "general" form type, right? Now, list down all the $3!=6$ permutations of $x_1,x_2,x_3$, and put them in the gene...
3 comments
Read more

IMO Shortlist 2022 C1

  Today we shall try IMO Shortlist $2022$ C1. A $\pm 1$-sequence is a sequence of $2022$ numbers $a_1, \ldots, a_{2022},$ each equal to either $+1$ or $-1$. Determine the largest $C$ so that, for any $\pm 1$-sequence, there exists an integer $k$ and indices $1 \le t_1 < \ldots < t_k \le 2022$ so that $t_{i+1} - t_i \le 2$ for all $i$, and$$\left| \sum_{i = 1}^{k} a_{t_i} \right| \ge C.$$ We claim that the answer is $\boxed{506}$. $506$ is the upper bound. Just consider the sequence $$+1,-1,-1,+1,+1,-1,-1,+1\dots,-1,-1,+1,+1,-1.$$ Here $1, -1, -1, 1$ is repeated $505$ times and $1,-1$ is concatted to it. Now,our sequence would be $a_1,a_3,a_4,a_5,a_7,\dots$ which on summing would give $506$. And clearly, this would give the upper bound. Now, we show that $506$ is attainable by every sequence. WLOG there are at least $1011$ positive numbers in the sequence. Then we choose $+1$ whenever we can. Let the sequence be $c_1,b_1,\dots, c_n,b_n$ where $c_i$ are ...
1 comment
Read more

New year with a new beginning! And a recap of 2024..and all the best for INMO 2025!

Hi everyone! Happy New Year :)  Thank you so much for 95k+ views!!! How was everyone's 2024? What are everyone's resolutions? ( Do write down in the comment section! And you can come back 1 year later to see if you made them possible!). A Better Mathematician  Well, technically a theoretical computer scientist.  I am so grateful to be allowed to study at CMI where I can interact with so many brilliant professors, access the beautiful library and obviously discuss mathematics ( sometimes non math too ) with the students.    And this year, I want to learn more mathematics and clear my fundamentals. I have become much worse in math actually. And hopefully, read some research papers too :)  And discuss a lot of mathematics with other people.  However, with that whole depressing 2024 year, I have lost a lot of my confidence in mathematics. And to be a better mathematician, I should gain the confidence that I can be a mathematician. And well, I am working on...
6 comments
Read more

Some Geometry Problems for everyone to try!

 These problems are INMO~ish level. So trying this would be a good practice for INMO!  Let $ABCD$ be a quadrilateral. Let $M,N,P,Q$ be the midpoints of sides $AB,BC,CD,DA$. Prove that $MNPQ$ is a parallelogram. Consider $\Delta ABD$ and $\Delta BDC$ .Note that $NP||BD||MQ$. Similarly, $NM||AC||PQ$. Hence the parallelogram. In $\Delta ABC$, $\angle A$ be right. Let $D$ be the foot of the altitude from $A$ onto $BC$. Prove that $AD^2=BD\cdot CD$. Note that $\Delta ADB\sim \Delta CDA$. So by similarity, we have $$\frac{AD}{BD}=\frac{CD}{AD}.$$ In $\Delta ABC$, $\angle A$ be right. Let $D$ be the foot of the altitude from $A$ onto $BC$. Prove that $AD^2=BD\cdot CD$. Let $D\in CA$, such that $AD = AB$.Note that $BD||AS$. So by the Thales’ Proportionality Theorem, we are done! Given $\Delta ABC$, construct equilateral triangles $\Delta BCD,\Delta CAE,\Delta ABF$ outside of $\Delta ABC$. Prove that $AD=BE=CF$. This is just congruence. N...
3 comments
Read more

INMO Scores and Results

Heya! INMO Results are out! Well, I am now a 3 times IMOTCer :D. Very excited to meet every one of you! My INMO score was exactly 26 with a distribution of 17|0|0|0|0|9, which was a fair grading cause after problem 1, I tried problem 6 next. I was hoping for some partials in problem 4 but didn't get any.  I am so so so excited to meet everyone! Can't believe my olympiad journey is going to end soon..  I thought to continue the improvement table I made last year! ( I would still have to add my EGMO performance and also IMO TST performance too) 2018-2019[ grade 8]:  Cleared PRMO, Cleared RMO[ State rank 4], Wrote INMO 2019-2020[ grade 9]:  Cleared PRMO, Cleared RMO[ State topper], Wrote INMO ( but flopped it) 2020-2021[grade 10]:  Cleared IOQM, Cleared INMO [ Through Girl's Quota] 2021-2022[grade 11]:  Wrote EGMO 2022 TST[ Rank 8], Qualified for IOQM part B directly, Cleared IOQM-B ( i.e INMO) [Through general quota],  2022-2023 [grade 12]:  Wrote E...
Post a Comment
Read more