Homework 1: Mathematical induction Problem 1 Denote by \( P(n) \) the following statement: \[ 1^3+2^3+\cdots+ n^3=\frac{n^2(n+1)^2}4.\] We can easily check that \( P(1) \) is true. This follows from the fact that \( \displaystyle P(1)\equiv\left( 1^3= \frac{1^2\cdot (1+1)^2}{4}\right) \). Assume now that \( P(k) \) is true for some integer \( k\geq \). We will prove that the proposition \( P(k+1) \) is true as well. We can write \begin{eqnarray*} 1^3+2^3+\cdots+ k^3+(k+1)^3&=&\left(1^3+2^3+\cdots+ k^3\right)+(k+1)^3\\ &=&\frac{k^2(k+1)^2}{4}+(k+1)^3=\frac{(k+1)^2\left(k^2+4(k+1)\right)}4\\ &=&\frac{(k+1)^2\cdot(k+2)^2}{4}. \end{eqnarray*}
Problem 2 Let \( P(n) \) be the following statement: We will prove that \( P(n) \) is true for every integer \( n\geq 1 \). The proposition \( P(1) \) is clearly true since \( \frac{1^2+1+2}2=2 \) and the plane can be partitioned into \( 2 \) regions using one line. Assume that \( P(k) \) is true for certain positive integer \( k \). We will prove the statement \( P(k+1) \). Since \( P(k) \) is true, the plane can be partitioned into \( \frac{k^2+k+2}2 \) regions \( P_1 \), \( P_2 \), \( \dots \), \( P_{\frac{k^2+k+2}2} \) using \( k \) lines \( l_1 \), \( l_2 \), \( \dots \), \( l_k \). Let us denote by \( \mathcal P \) the set of all regions in the partition. Let us denote by \( \overrightarrow{v}_1 \), \( \overrightarrow{v}_2 \), \( \dots \), \( \overrightarrow{v}_k \) the vectors of the \( k \) lines used to partition the plane. Since this set of vectors is finite there is a vector \( \overrightarrow{v}_{k+1} \) in the plane that is not parallel to any of the given vectors. Let us consider the set \( G \) of all lines parallel to \( \overrightarrow{v}_{k+1} \) that pass through intersection points of the lines \( l_1 \), \( \dots \), \( l_k \). Since the number of elements of \( G \) is finite, there exists a line \( l_{k+1} \) parallel to \( \overrightarrow{v}_{k+1} \) that does not belong to \( G \). This line intersects each of \( l_1 \), \( l_2 \), \( \dots \), \( l_{k} \). Let us denote by \( D_1 \), \( D_2 \), \( \dots \), \( D_k \) the intersection points of \( l_{k+1} \) with these lines, and let us assume without loss of generality that their order is \( D_1- D_2-\cdots - D_k \).
Therefore \( k+1 \) new region is created, hence the total number of regions created by the lines \( l_1 \), \( l_2 \), \( \dots \), \( l_{k+1} \) is \[ \frac{k^2+k+2}2+k+1=\frac{k^2+3k+4}2=\frac{(k+1)^2+(k+1)+2}2.\] Problem 3 Given \( 3n \) points \( A_1,A_2,\dots,A_{3n} \) in the plane, assume that no three of them collinear. Prove that it is possible to construct \( n \) disjoint triangles with vertices at the points \( A_i \). We use induction. For \( n=1 \) the assertion is obvious. Assume that it is true for a positive integer \( n \). Let \( A_1,A_2,\dots,A_{3n+3} \) be given \( 3n+3 \) points, and let w.l.o.g. \( A_1A_2 \dots A_m \) be their convex hull. Among all the points \( A_i \) distinct from \( A_1,A_2 \), we choose the one, say \( A_k \), for which the angle \( \angle A_kA_1A_2 \) is minimal (this point is uniquely determined, since no three points are collinear). The line \( A_1A_k \) separates the plane into two half-planes, one of which contains \( A_2 \) only, and the other one all the remaining \( 3n \) points. By the inductive hypothesis, one can construct \( n \) disjoint triangles with vertices in these \( 3n \) points. Together with the triangle \( A_1A_2A_k \), they form the required system of disjoint triangles. Problem 4 We can easily check that \( 5^n> n! \) for \( n\in\{1,2,\dots, 11\} \) and that for \( n=12 \) we have \( 5^n> n! \). We will now prove by induction that \( 5^n< n! \) for all \( n\geq 12 \). Denote by \( P(n) \) the statement \( 5^n< n! \). Assume that \( P(k) \) is true for some \( k\geq 12 \). Then \( 5^{k+1}=5^k\cdot 5< k!\cdot 5< k!\cdot (k+1)=(k+1)! \). Therefore \( P(k+1) \) is true as well. Hence the required integers are the numbers from the set \( \{1,2,\dots, 11\} \). Problem 5 Consider the polynomial \( p(x)=a_0x^k+a_1x^{k-1}+\dots+ a_k \) with integer coefficients. The polynomial \( p \) is said to be divisible by an integer \( m \) if \( p(x) \) is divisible by \( m \) for all integers \( x \). Prove that if \( p(x) \) is divisible by \( m \), then \( k!a_0 \) is also divisible by \( m \). We will prove the result by induction on \( k \). It trivially holds for \( k=0 \). Assume that the statement is true for some \( k-1 \), and let \( p(x) \) be a polynomial of degree \( k \). Let us set \( p_1(x)= p(x+1)-p(x) \). Then \( p_1(x) \) is a polynomial of degree \( k-1 \) with leading coefficient \( ka_0 \). Also, \( m\mid p_1(x) \) for all \( x\in\mathbb{Z} \) and hence by the inductive assumption \( m\mid (k-1)!\cdot ka_0=k!a_0 \). This completes the induction. Problem 6 Prove that for every positive integer \( n \) there exist positive integers \( a_{11} \), \( a_{21} \), \( a_{22} \), \( a_{31} \), \( a_{32} \), \( a_{33} \), \( \dots \), \( a_{n1} \), \( a_{n2} \), \( \dots \), \( a_{nn} \) such that \[ a_{11}^2=a_{21}^2+a_{22}^2=a_{31}^2+a_{32}^2+a_{33}^2=\cdots=a_{n1}^2+\cdots+a_{nn}^2.\] Induction on \( n \): The statement holds for \( n=1 \). Assume that it holds for some \( n \) and let us prove it for \( n+1 \). Assume that \( a_{11} \), \( \dots \), \( a_{nn} \) are the numbers satisfying \[ a_{11}^2=a_{21}^2+a_{22}^2=a_{31}^2+a_{32}^2+a_{33}^2=\cdots=a_{n1}^2+\cdots+a_{nn}^2.\] Let us define \( a_{ij}^{\prime}=5a_{ij} \) for \( 1\leq j\leq i\leq n \). Let us define \( a^{\prime}_{n+1,i}=3a_{n,i} \) for \( 1\leq i\leq n \), and \( a^{\prime}_{n+1,n+1}=4a_{11} \). Then the relations hold for numbers \( a^{\prime}_{11}, a^{\prime}_{21},a^{\prime}_{22},\dots, a^{\prime}_{n+1,n+1} \). Problem 7 Consider the set \( \mathcal F \) of all injective functions \( f:\mathbb N\to\mathbb N \) that satisfy \[ f(2x)+f(x)f(y)=f(x\cdot y)+2f(x),\;\;\mbox{for all }x,y\in\mathbb N.\] Determine \( \displaystyle\min_{f\in\mathcal F}\left\{f(2012)\right\}. \) Placing \( x=2 \) and \( y=2 \) in the original equation yields: \( f(4)+f(2)^2=f(4)+2f(2) \) which implies that \( f(2)=2 \). Placing \( x=1 \) and \( y=1 \) gives \( f(2)+f(1)^2=f(1)+2f(1) \) which implies \( f(1)^2-3f(1)+2=0 \) and \( f(1)\in\{1,2\} \). If we assume that \( f(1)=2 \), then setting \( x=1 \) in the original equation implies that \( f(2)+2f(y)=f(y)+2\cdot 2 \) hence \( f(y)=2 \) for all \( y \) and this is not a function from \( \mathcal F \). Assume therefore that \( f(1)=1 \). Placing \( y=1 \) in the original equation yields \( f(2x)=2f(x) \). Using induction we now obtain \( f(2^n)=2^n \). The original equation implies that \( f(x)f(y)=f(xy) \). If \( x=p_1^{\alpha_1}\cdots p_k^{\alpha_k} \) is the prime factorization of \( x \) then we have \( f(x)=f(p_1)^{\alpha_1}\cdots f(p_k)^{\alpha_k} \). Since \( 2012=2^2\cdot 503 \) is the prime factorization of \( 2012 \) we have that \( f(2012)=4\cdot f(503) \). Since \( f \) is injective we must have \( f(503)\not\in\{f(1),f(2)\}=\{1,2\} \) hence \( f(503)\geq 3 \) and \( f(2012)\geq 12 \). On the other hand, such an \( f \) exists. We may take \( f(1)=1 \), \( f(2)=2 \), \( f(3)=503 \), \( f(503)=3 \), \( f(p)=p \) for every other prime \( p \), and \( f(x)=f(p_1)^{\alpha_1}\cdots f(p_k)^{\alpha_k} \) if \( x=p_1^{\alpha_1}\cdots p_k^{\alpha_k} \) is the prime factorization of \( x \). Problem 8 The sequence \( (a_n)_{n=1}^{\infty} \) is defined as \( a_0=2 \), \( a_1=\frac52 \), and \( a_{n+1}=a_n(a_{n-1}^2-2)-\frac52 \), for \( n\geq 1 \). Prove that \[ 3\log_2{[a_n]}=2^n-(-1)^n,\] where \( [x] \) is the integral part of \( x \). The first few values are easily verified to be \( 2^{r_n}+ 2^{-r_n} \), where \( r_0=0 \), \( r_1=r_2=1 \), \( r_3=3 \), \( r_4=5 \), \( r_5=11, \:\dots \) . Let us put \( a_n=2^{r_n}+2^{-r_n} \) (we will show that \( r_n \) exists and is integer for each \( n \)). A simple calculation gives us \( a_n(a_{n-1}^2-2)=2^{r_n+2r_{n-1}}+2^{-r_n-2r_{n-1}}+ 2^{r_n-2r_{n-1}}+2^{-r_n+2r_{n-1}}. \) If an array \( q_n \), with \( q_0=0 \) and \( q_1=1 \), is set so as to satisfy the linear recurrence \( q_{n+1}=q_n+2q_{n-1} \), then it also satisfies \( q_n-2q_{n-1}=-(q_{n-1}-2q_{n-2})=\cdots= (-1)^{n-1}(q_1-2q_0)=(-1)^{n-1}. \) Assuming inductively up to \( n \) \( r_i=q_i \), the expression for \( a_n(a_{n-1}^2-2)=a_{n+1}+a_1 \) reduces to \( 2^{q_{n+1}}+2^{-q_{n+1}}+u_1 \). Therefore, \( r_{n+1}=q_{n+1} \). The solution to this linear recurrence with \( r_0=0 \), \( r_1=1 \) is \( r_n=q_n=\frac{2^n-(-1)^n}3 \), and since \( [a_n]=2^{r_n} \) for \( n\geq0 \), the result follows. Remark. One could simply guess that \( a_n=2^{r_n}+2^{-r_n} \) for \( r_n=\frac{2^n-(-1)^n}3 \), and then prove this result by induction. |
2005-2017 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax Home | Olympiads | Book | Training | IMO Results | Forum | Links | About | Contact us |