INTRODUCING 5 - days-a-week problem solving session for Math Olympiad and ISI Entrance. Learn More

# Understand the problem

[/et_pb_text][et_pb_text _builder_version="3.27.4" text_font="Raleway||||||||" background_color="#f4f4f4" box_shadow_style="preset2" custom_margin="10px||10px" custom_padding="10px|20px|10px|20px" _i="1" _address="0.0.0.1"]For each positive integer $n$ let  $$x_n=p_1+\cdots+p_n$$  where  $p_1,\ldots,p_n$   are the first $n$ primes. Prove that for each positive integer $n$, there is an integer $k_n$ such that   $x_n[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row _builder_version="3.27" _i="1" _address="0.1"][et_pb_column type="4_4" _builder_version="3.25" custom_padding="|||" custom_padding__hover="|||" _i="0" _address="0.1.0"][et_pb_accordion open_toggle_text_color="#0c71c3" _builder_version="3.27" toggle_font="||||||||" body_font="Raleway||||||||" text_orientation="center" custom_margin="10px||10px" _i="0" _address="0.1.0.0"][et_pb_accordion_item title="Source of the problem" open="on" _builder_version="3.27" hover_enabled="0" _i="0" _address="0.1.0.0.0"]SMO (senior)-2014 stage 2 problem 4

[/et_pb_accordion_item][et_pb_accordion_item title="Topic" _builder_version="3.27" hover_enabled="0" _i="1" _address="0.1.0.0.1" open="off"]Number Theory[/et_pb_accordion_item][et_pb_accordion_item title="Difficulty Level" _builder_version="3.27" hover_enabled="0" _i="2" _address="0.1.0.0.2" open="off"]Medium[/et_pb_accordion_item][et_pb_accordion_item title="Suggested Book" _builder_version="3.27" hover_enabled="0" _i="3" _address="0.1.0.0.3" open="off"]Excursion in Mathematics

[/et_pb_text][et_pb_tabs active_tab_background_color="#0c71c3" inactive_tab_background_color="#000000" _builder_version="3.27.4" tab_text_color="#ffffff" tab_font="||||||||" background_color="#ffffff" hover_enabled="0" _i="2" _address="0.1.0.2"][et_pb_tab title="Hint 0" _builder_version="3.27" hover_enabled="0" _i="0" _address="0.1.0.2.0"]Do you really need a hint? Try it first!

[/et_pb_tab][et_pb_tab title="Hint 1" _builder_version="3.27.4" hover_enabled="0" _i="1" _address="0.1.0.2.1"]We have $P_1 = 2 , P_=3 , P_3=5 , P_4 =7 , P_5 = 11 \ and \ so \ on ....$. Now to understand the expression   $x_n  ,  observe .   $For \ n=1 \ , \ 2 < 2^2 < 2+3$  $For \ n=2 \ , \ 2+3 < 3^2 < 2+3+5$ $For \ n=3 \ , \ 2+3+5 < 4^2 < 2+3 +5+7$ $For \ n=4 \ , \ 2+3 +5+7 < 5^2 <2+3 +5+7 +11$ Now proceed to prove $\forall n \geq 5$ .[/et_pb_tab][et_pb_tab title="Hint 2" _builder_version="3.27.4" hover_enabled="0" _i="2" _address="0.1.0.2.2"]Observe  $\forall n \geq 5$ we have $P_n > (2n-1)$. [where $n \in Z^+$] Then try to use  $x_n = P_1 + P_2 + ...+P_5+..... +P_n > 1 +3 + ....+ 9 +... (2n-1) = n^2 \\ \Rightarrow x_n > n^2 , \forall n \geq 5[where \ n \in Z^+]$ .[/et_pb_tab][et_pb_tab title="Hint 3" _builder_version="3.27.4" hover_enabled="0" _i="3" _address="0.1.0.2.3"]Think if $x_n=P_1 + P_2 + .... + P_5 +...P_n = b^2 for \ some \ n , b \in Z^+$ , then we are done . If not so , then think $m$ be the largest non negative integer such that  $(n+m)^2 < x_n$ . Now note that the next perfect square is $(n+m+1)^2$ . Observe that if we can prove that   $(n+m+1)^2 - (n+m)^2 = (2n+ 2m +1) \geq P_{n+1}$  , then we are done . Now try to verify this claim .[/et_pb_tab][et_pb_tab title="Hint 4" _builder_version="3.27.4" hover_enabled="0" _i="4" _address="0.1.0.2.4"]

Suppose our claim is not true  i.e. $P_n < 2n + 2m +1$ . So,   $P_n < 2n + 2m +1 \\ \Rightarrow 2n+ 2m \geq P_n , \forall n \in Z^+ \\ \Rightarrow (2n +2m-2)+(2n+ 2m -4)+.....2m \geq P_n + P_{n-1}+......+P_1 \\ \Rightarrow n^2 + 2mn -n \geq P_n + P_{n-1}+......+P_1 \\ \Rightarrow n^2 + 2mn -n \geq x_n \\ \Rightarrow n^2 + 2mn +m^2 > n^2 + 2mn -n\geq x_n \\ \Rightarrow (n+m)^2 > x_n$ .  Contradiction!  since we have assumed $x_n = P_1 + P_2+......+P_{n-1} > (n+m)^2$ . Thus ,$(n+m+1)^2 \in (x_n , x_{n+1})$  .     [/et_pb_tab][/et_pb_tabs][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3" min_height="12px" custom_margin="50px||50px" custom_padding="20px|20px|20px|20px" _i="3" _address="0.1.0.3"]