What are the minimum and maximum values?

Proving/Determining maximum/minimum values ? What are the common methods? (see details)?

• Determine the maximum value of m^2 + n^2 where m,n are elements of {1,2,3,...,2007} and (n^2 - mn -m^2)^2 = 1.

• Answer:

  Your problem is one of the most interesting I've encountered in Yahoo Answers! I can suggest You 2 very different methods, let's begin with the more complicated. It involves 2nd degree Diophantine equations, namely Pelle's equation /please follow the link below for more details/. You need to find integer solution(s) of the equation: (n² - mn - m²)² = 1, here m, n=1,2,..2007 with the greatest possible m and n, that leads /eventually exchanging notations/ to (A) m² ± mn - n² = 1, multiply by 4: 4m² ± 4mn - 4n² = 4, or 4m² ± 4mn + n² - 5n² = 4, or (2m ± n)² - 5n² = 4, or denoting (B) 2m ± n = x, n = y we obtain the equation (C) x² - 5y² = 4 Some of its integer solutions are x1=2, y1=0; x2=3, y2=1; x3=7, y3=3 and according the general theory of 2nd degree Diophantine equations we must solve first the Pell's equation /see link/: (D) u² - 5v² = 1 with obvious solution u_{0} = 1, v_{1} = 0. Its fundamental solution is u_{1} = 9, v_{1} = 4 and all its solutions can be obtained by recurrence formulas: (***) u_{k+1} = 9u_{k} + 5*4v_{k} (***) v_{k+1} = 4u_{k} + 9v_{k}, /k=0,1,2,.../ For k = 0,1,2 we obtain (1,0), (9,4) and (161,72). Now the solutions of (C) can be obtained by: x = ux' + 5vy', y = vx' + uy' where (u,v) runs all solutions of (D) and (x',y') is one of 3 listed above solutions of (C), so we'll have: x = 3u, y = 2v x = 3u + 5v, y = u + 3v x = 7u + 15v, y = 3u + 7v, then /look (B) above/ m = (x ± y)/2, n = y yield the following 6 expression sets: (1) m = u - v, n = 2v (2) m = u + v, n = 2v (3) m = u + v, n = u + 3v (4) m = 2u + 4v, n = u + 3v (5) m = 2u + 4v, n = 3u + 7v (6) m = 5u + 11v, n = 3u + 7v For (u,v) = (1,0), (9,4), (161,72) they produce some pairs like (m, n) = (1, 0), (1, 1), (1, 2), (2, 3), (5, 3), (5, 8), (13, 8), etc. The last expression (6) above produces for u=161 and v=72 the following: m=1597; n=987 - this is the last solution of (A) with m,n < 2007 /this is the reason we'll not need more solutions of (D) above/. Comparing it with all other generated above, we obtain: max(m² + n²) = 1597² + 987² = 3524578, and this is the answer to Your problem! But in 21st century there is another very simple method: write a computer program like the following 2 lines of code for m=1 to 2007 do for n=1 to 2007 do if abs(m*m - m*n - n*n) = 1 then Print(m, n, m*m + n*n)) Run it, leaving the machine to do all work, the output is: m n m² + n² 1; 1; 2 2; 1; 5 3; 2; 13 5; 3; 34 8; 5; 89 13; 8; 233 21; 13; 610 34; 21; 1597 55; 34; 4181 89; 55; 10946 144; 89; 28657 233; 144; 75025 377; 233; 196418 610; 377; 514229 987; 610; 1346269 1597; 987; 3524578 - the answer again, thanks for the neat problem! P.S. (EDIT - after having read absird's answer) Congratulations for Your excellent observation! You are perfectly right, all solutions of the considered equation are exactly the consequent Fibonacci numbers, so the answer is the last pair, less than 2007. Here is the proof. Look at (1) above: m = u - v, n = 2v, add them now: (u - v) + 2v = u + v, You obtain u - v, 2v, u + v, go on the same way adding the last 2: u-v, 2v, u+v, u+3v, 2u+4v, 3u+7v, 5u+11v, 8u+18v, . . etc Take 2nd and 3rd of this sequence: notice this is exactly (2) above /You can interchange m and n, the equation is symmetric in respect to them/! Take 3rd and 4th: they are listed under (3) above and so on, until You find 3u+7v and 5u+11v under (6). Now if You add these and take the pair 5u+11v and 8u+18v You can rewrite them as: 5u + 11v = (9u + 20v) - (4u + 9v) 8u + 18v = 2(4u + 9v) Now look at (***) above: 9u + 20v and 4u + 9v ARE EXACTLY components of the next pair - solution of Pell's equation, say (u',v'), so 5u + 11v = u' - v'; 8u + 18v = 2v' and thereafter the sequence u' - v', 2v', u' + v', u' + 3v', 2u' + 4v',. . etc. repeats. Starting with u_{0} = 1, v_{0} = 0 now obviously our procedure requires infinitely many times to add every 2 consequent numbers, i.e. generates namely all Fibonacci numbers. When I answered, I hesitated a little whether to add a fragment like this with a note on appearing Fibonacci numbers, but the text was already too long, so I decided to add a star, all the problem's beauty fully deserves it, I noticed You've done the same. Now, seeing Your sharp eye and the deep interest on the subject You've shown, I felt obliged. Of course You might ask if there is more straightforward way to bring the things to the Fibonacci numbers without considering Pell's equation etc. - well, I can't suggest such and I'm afraid it is inevitable - You have just to solve a 2nd degree Diophantine equation and that 5 in (D) and sqrt(5) in the well-known Binet's expression for f_n make the appearance of Fibonacci numbers now not surprising at all! Once again congratulations for Your answer and the whole work You've done!