Problem Solving | Induction

We look at the problem solving technique of induction and give a few examples including a solution to a problem from the 1995 Russian Math Olympiad.

If you are going to use an ad-blocker, considering using brave and tipping me BAT!

Books I like:

Abstract Algebra:

Differential Forms:

Number Theory:

Analysis:

Calculus:

My Filming Equipment:

[Fun_maths]

I already knew this but this still helps with understanding how to use it

[accountname]

Your youtube channel is legit better than most undergrad classes

[rishavmondal]

Hi sir, I just love your problem solving class . I would like if you come up with more and more Olympiad problems (of national level or international level) and also Putnam questions. I would love to see explanation of questions on geometry, combinatorics by you.

[elrichardo]

Nice to see this channel branching out to high-school contest math!

[youssefamen]

Thx for hard work prof. Can u take a look at Putnam 2005 B6

[sarmadsultan]

You are a very good teacher man, appreciated!

[pratikmaity]

Hi Michael, hope you are fine. Here is a nice problem you can make a video on: if n is a natural number greater than 1 then n! can never be a perfect square. I know many people are aware of this problem but still kindly make a video on this one. Thanks

[easymathematik]

The example from the russian math olympiad uses a nice way of writing down binomials.

(n+m)^2 + (n-m)^2 = 1/2 ( (2n)^2 + (2m)^2 )

It is a very standart identity in my opinion.

[jimallysonnevado]

Please make a video about proof by infinite descent. It may be helpful in solving problems too.

[danielflynn]

For the first one, note that 2n+1 is always odd if n>=0 and therefore:
5^2n+1 + 2^2n+1 = a mod 7 =>
5^2n+1 + (-5)^2n+1 = a mod 7 =>
5^2n+1 - 5^2n+1 = 0 mod 7 = a mod 7
Therefore 7 divides 5^2n+1 + 2n+1
This holds for any m and n for divisor m+n
I know it's not induction, just thought it was a nice method

[jimschneider]

Late to the party, but ... at 3:00, your base case is k=0, so your induction hypothesis should assume that the theorem is true for some k >= 0, not k >= 1.

[throxs]

quick question. Shouldn't you have adressed a1 = 1 in the base case as wel? because if you only assume a0 = 0, you can't use the induction hypothesis that requires both a_{k} and a_{k-1}?

[michaelz]

It actually suffices to just assume the condition for m = n + 1. For then you get the difference equation (1/2)(a_{2n+2} - 2a_{2n + 1} + a_{2n}) = 1. The theory of difference equations then says the solution is of the form n^2 + cn + d, and then plugging in n = 0 and 1 gives a_n = n^2. (But this probably is too advanced for a high school contest).

[fu]

There are mistake in question one
Doing the base case with n=0, but supposing true for some k>=1

[blackmephistopheles]

Why not just test the claim in the recurrence relation?
(m+n)² + (m-n)² = m²+2mn+n²+m²-2mn+n² = 2m²+2n² = (1/2)(4m²+4n²) = (1/2) [(2m)²+(2n)²].

[get]

As some suggest below, just conjecture a polynomial solution and then use guess check

Solved the problem without using induction:

Given a[1] = 1, and
a[m+n] + a[m-n] = 1/2*(a[2m] + a[2n])

Putting m = n = 0,
2*a[0] = a[0], or a[0] = 0

Putting n = 0,
a[m] + a[m] = 1/2*(a[2m] + a[0]), or
a[2m] = 4*a[m]

This means a[2] = 4*a[1] = 4, a[4] = 4*a[2] = 16, a[8] = 4*a[4] =

Now putting n = 1,
a[m+1] + a[m-1] = 1/2*(a[2m] + a[2]) = 1/2*(4*a[m] + 4) = 2*a[m] + 2, or
(a[m+1] - a[m]) - (a[m] - a[m-1]) = 2

Continuing, we have
(a[m+1] - a[m]) - (a[m] - a[m-1]) = 2
(a[m] - a[m-1]) - (a[m-1] - a[m-2]) = 2
....
....
(a[3] - a[2]) - (a[2] - a[1]) = 2
(a[2] - a[1]) - (a[1] - a[0]) = 2
Adding these,
(a[m+1] - a[m]) - (a[1] - a[0]) = 2*m, or
a[m+1] - a[m] = 2*m + 1

Continuing similarly, we also have
a[m+1] - a[m] = 2*m + 1
a[m] - a[m-1] = 2*(m-1) + 1
....
....
a[1] - a[0] = 2*(0) + 1
Adding these,
a[m+1] - a[0] = 2*(0+1+2+....+m) + (m+1), or
a[m+1] - 0 = 2*m*(m+1)/2 + (m+1) = m² + 2*m + 1, which means
a[m+1] = (m+1)²

So, a[1995] = (1995)² = 3, 980, 025

[demenion]

just a minor addition to the video: there are problems that are easier to solve via induction if you adjust the induction step. for example, it might be easier to show that the case k+2 is true and also k-1 is true if k is. or it might be easy to show that 2k is true and m=2k-1 is true if k is. you could also subdivide your cases by their residues mod some small number (2, 3, 4...) and then use several base cases. such induction steps are not very common, but sometimes really convenient

[caesar_cipher]

I think the video proves a(m)=m² is one of the possible solutions of the recurrence relation. But it does not mean it is the only possible solution - is that right ?

[sophieward]

Would this work for a proof?

After experimenting, I conjecture that a_n = n^2. First, note that 1^2 = 1 = a_1. Consider each side of the defining recurrence relation, and replace the sequence notation with the conjectured formula. On the left we have (m+n)^2 + (m-n)^2 = m^2 + 2mn + n^2 + m^2 - 2mn + n^2 = 2m^2 + 2n^2. On the right, we have 1/2 ((2m)^2 + (2n)^2) = 1/2 (4m^2 + 4n^2) = 2m^2 + 2n^2, which is the same as we have on the left. Our expression satisfies all necessary requirements, therefore a_n = n^2 for all n.