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💜

Comments

  1. 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. 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. Yep I think both work! Thanks for sharing!

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

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

    ReplyDelete

Post a Comment

Popular posts from this blog

Geometry ( Finally!!!)

 This is just such an unfair blog.  Like if one goes through this blog, one can notice how dominated  Algebra is!! Like 6 out of 9 blog post is Algebra dominated -_- Where as I am not a fan of Algebra, compared to other genres of Olympiad Math(as of now). And this was just injustice for Synthetic Geo. So this time , go geo!!!!!!!!!!!  These problems are randomly from A Beautiful Journey through Olympiad Geometry.  Also perhaps I will post geo after March, because I am studying combi.  Problem:  Let $ABC$ be an acute triangle where $\angle BAC = 60^{\circ}$. Prove that if the Euler’s line of $\triangle ABC$ intersects $AB$ and $AC$ at $D$ and $E$, respectively, then $\triangle ADE$ is equilateral. Solution:  Since $\angle A=60^{\circ}$ , we get $AH=2R\cos A=R=AO$. So $\angle EHA=\angle DOA.$ Also it's well known that $H$ and $O $ isogonal conjugates.$\angle OAD =\angle EAH.$ By $ASA$ congruence, we get $AE=AD.$ Hence $\triangle ADE$ is equilateral....

Problems I did this week [Jan8-Jan14]

Yeyy!! I am being so consistent with my posts~~ Here are a few problems I did the past week and yeah INMO going to happen soon :) All the best to everyone who is writing!  I wont be trying any new problems and will simply revise stuffs :) Some problems here are hard. Try them yourself and yeah~~Solutions (with sources) are given at the end! Problems discussed in the blog post Problem1: Let $ABC$ be a triangle whose incircle $\omega$ touches sides $BC, CA, AB$ at $D,E,F$ respectively. Let $H$ be the orthocenter of $DEF$ and let altitude $DH$ intersect $\omega$ again at $P$ and $EF$ intersect $BC$ at $L$. Let the circumcircle of $BPC$ intersect $\omega$ again at $X$. Prove that points $L,D,H,X$ are concyclic. Problem 2: Let $ ABCD$ be a convex quadrangle, $ P$ the intersection of lines $ AB$ and $ CD$, $ Q$ the intersection of lines $ AD$ and $ BC$ and $ O$ the intersection of diagonals $ AC$ and $ BD$. Show that if $ \angle POQ= 90^\circ$ then $ PO$ is the bisector of $ \angle AOD$ ...

Just spam combo problems cause why not

This post is mainly for Rohan Bhaiya. He gave me/EGMO contestants a lot and lots of problems. Here are solutions to a very few of them.  To Rohan Bhaiya: I just wrote the sketch/proofs here cause why not :P. I did a few more extra problems so yeah.  I sort of sorted the problems into different sub-areas, but it's just better to try all of them! I did try some more combo problems outside this but I tried them in my tablet and worked there itself. So latexing was tough. Algorithms  "Just find the algorithm" they said and they died.  References:  Algorithms Pset by Abhay Bestrapalli Algorithms by Cody Johnson Problem1: Suppose the positive integer $n$ is odd. First Al writes the numbers $1, 2,\dots, 2n$ on the blackboard. Then he picks any two numbers $a, b$ erases them, and writes, instead, $|a - b|$. Prove that an odd number will remain at the end.  Proof: Well, we go $\mod 2$. Note that $$|a-b|\equiv a+b\mod 2\implies \text{ the final number is }1+2+\dots ...

IMO 2023 P2

IMO 2023 P2 Well, IMO 2023 Day 1 problems are out and I thought of trying the geometry problem which was P2.  Problem: Let $ABC$ be an acute-angled triangle with $AB < AC$. Let $\Omega$ be the circumcircle of $ABC$. Let $S$ be the midpoint of the arc $CB$ of $\Omega$ containing $A$. The perpendicular from $A$ to $BC$ meets $BS$ at $D$ and meets $\Omega$ again at $E \neq A$. The line through $D$ parallel to $BC$ meets line $BE$ at $L$. Denote the circumcircle of triangle $BDL$ by $\omega$. Let $\omega$ meet $\Omega$ again at $P \neq B$. Prove that the line tangent to $\omega$ at $P$ meets line $BS$ on the internal angle bisector of $\angle BAC$. Well, here's my proof, but I would rather call this my rough work tbh. There are comments in the end! Proof Define $A'$ as the antipode of $A$. And redefine $P=A'D\cap (ABC)$. Define $L=SP\cap (PDB)$.  Claim1: $L-B-E$ collinear Proof: Note that $$\angle SCA=\angle SCB-\angle ACB=90-A/2-C.$$ So $$\angle SPA=90-A/2-C\implies \ang...

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...

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...

Challenging myself? [Jan 15-Jan 27]

Ehh INMO was trash. I think I will get 17/0/0/0-1/3-5/10-14, which is def not good enough for qualifying from 12th grade. Well, I really feel sad but let's not talk about it and focus on EGMO rather.  INMO 2023 P1 Let $S$ be a finite set of positive integers. Assume that there are precisely 2023 ordered pairs $(x,y)$ in $S\times S$ so that the product $xy$ is a perfect square. Prove that one can find at least four distinct elements in $S$ so that none of their pairwise products is a perfect square. I will use Atul's sol, cause it's the exact same as mine.  Proof: Consider the graph $G$ induced by the elements of $S$ and edges being if the products are perfect squares. Note that if $xy = a^2$ and $xz = b^2$, then $yz = \left( \frac{ab}{x} \right)^2$, since its an integer and square of a rational number its a perfect square and so $yz$ is an edge too. So the graph is a bunch of disjoint cliques, say with sizes $c_1, c_2, \cdots, c_k$. Then $\sum_{i=1}^k c_i^2 = 2023$, which ...

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...

Some random problems

  I know, I know. Different font indeed. I have deleted a few of my MSE answers. I felt they weren't that good in quality. And a few questions are from my prev aops account which I have deactivated now. I also have posted 10 IOQM types of problems. These can be used while preparing for IOQM. Problem: Prove that $\dfrac{ab}{c^3}+\dfrac{bc}{a^3}+\dfrac{ca}{b^3}> \dfrac{1}{a}+\dfrac{1}{b}+\dfrac{1}{c}$, where $a,b,c$  are different positive real numbers.  Proof: Note that by AM-GM $$\frac{ab}{c^3}+\frac{bc}{a^3}\ge \frac{2b}{ac}$$ and we also have $$\frac {b}{ac}+\frac{c}{ab}\ge \frac{2}{a}$$. Hence, $$\sum_{cyc}\frac{ab}{c^3}\ge\sum_{cyc}\frac{b}{ac}\ge\sum_{cyc}\frac{1}{a}$$ where everything we got is by applying AM-GM on $2$ terms and then dividing by $2$. USA TST 2007: Triangle $ABC$ which is inscribed in circle $\omega$. The tangent lines to $\omega$ at $B$ and $C$ meet at $T$. Point $S$ lies on ray $BC$ such that $AS$ is perpendicular to $AT$. Points $B_1$ and $C_1...

Introduction

  Hey Everyone!! This is my first Blog post. So let me give a brief introduction about myself. I am Sunaina Pati. I love solving Olympiad math problems,  learning crazy astronomical facts , playing hanabi and anti-chess, listening to Kpop , love making diagrams in Geogebra and  teaching other people maths 😊 . I love geometry , number theory and Combinatorics . I am starting this blog to keep myself a bit motivated in doing studies 😎 . Right now, I am planning to write walkthroughs on some of the best problems I tried over the week which can refer for hints 'cause solutions contain some major spoilers and one learns a lot while solving the problem on his own rather than seeing solutions . Also, there will be some reviews about Kpop songs, study techniques, my day to day lifestyles,exam reviews and ofc some non-sense surprises 😂.  I am planning to  try  posting every week on Sundays or Saturdays ( most probably) ! Though there is no guarantee about when I ...