Author Topic: Interesting induction questions (Read 6235 times) Tweet Share

Mahan · « **on:** October 30, 2016, 11:43:16 pm »

Hi all,
I just wanted to share an interesting induction question.The idea behind the question is not what we usually use to solve the majority of induction questions. So I thought, it would be interesting to try to solve this question.

RuiAce · « **Reply #1 on:** October 30, 2016, 11:45:54 pm »

What exactly does every 2ⁿ⁺¹ natural number mean here?

Mahan · « **Reply #2 on:** October 30, 2016, 11:49:33 pm »

Quote from: RuiAce on October 30, 2016, 11:45:54 pm

What exactly does every 2ⁿ⁺¹ natural number mean here?

It is an induction question. It means if you pick any natural number n, i.e n=10, and if you choose 2^(n+1) natural numbers, you can always choose 2^(n) natural numbers from those 2^(n+1) such that the sum is divisible by 2^(n). I hope that clarifies the question.

RuiAce · « **Reply #3 on:** October 30, 2016, 11:52:15 pm »

Quote from: Mahan on October 30, 2016, 11:49:33 pm

It is an induction question. It means if you pick any natural number n, i.e n=10, and if you choose 2^(n+1) natural numbers, you can always can choose 2^(n) natural numbers from those 2^(n+1) such that the sum is divisible by 2^(n). I hope that clarifies the question.

And these 2ⁿ⁺¹ numbers have no upper bound? So we're allowed to pick any 2ⁿ⁺¹ elements of the natural numbers we like?

So take n=10, then if we pick any 2¹¹ elements of the natural numbers (i.e. one of them could be say 2¹²) then the sum of 2¹⁰ of such elements must be divisble by 2¹⁰?

Seems like a nice question but we need to clear up the technicalities

Mahan · « **Reply #4 on:** October 31, 2016, 12:09:04 am »

Quote from: RuiAce on October 30, 2016, 11:52:15 pm

And these 2ⁿ⁺¹ numbers have no upper bound? So we're allowed to pick any 2ⁿ⁺¹ elements of the natural numbers we like?

So take n=10, then if we pick any 2¹¹ elements of the natural numbers (i.e. one of them could be say 2¹²) then the sum of 2¹⁰ of such elements must be divisble by 2¹⁰?

Seems like a nice question but we need to clear up the technicalities

Yes that's correct.
2^10 is the number of natural numbers you can pick and there is no upper bound for the natural numbers you chose.

RuiAce · « **Reply #5 on:** November 01, 2016, 06:28:00 am »

Warning: What follows gone tremendously outside "Mathematics Extension 2" territory. Concepts here are NOT examinable and should NOT be treated as the standard of the course. Technically, not even set theory is examinable.

Disclaimer: Not all my own material. Credit shared to someone who helped me out. Which leads to query - what is the source of this question? Was it actually doable by 4U methods $\text{Let }S_{n} \subset \mathbb{N}\text{ s.t. }|S_n|=2^{n+1}\\ \text{Then, suppose }\exists T_n \subset S_n\text{ s.t. }|T_n| = 2^n$
$\text{Let }P(n)\text{ be the proposition that }\forall x_j \in T_n\quad (x_i = x_j \iff i = j)\\ 2^n \mid \sum_{j=1}^{2^n}x_j$
Note that existential quantification is assumed at the start as per the wording of the question. If universal quantification were chosen, then for n=1, take the set {1, 2, 3, 4}. Then clearly 1+2 = 3 and 3 is not divisible by 2.
$\text{Consider }P(1):\\ |S_1| = 4\text{ and }|T_1|=2\\ \text{Observe that the set }T_n\text{ must be formed such that}\\ \text{the sum of the elements in }T_n\text{ is divisible by 2.}\\ \text{Further, note that the sum of two even, or the sum of two odd numbers, is divisible by 2.}$
$\text{By the pigeonhole principle, since }|S_1|=4\\ \text{There must be }\left\lceil \frac{4}{2}\right\rceil = 2\text{ numbers in }S_1\text{ of the same parity}\\ \text{i.e. they are both odd or both even}$
$\text{Hence, take }T_n=\{\text{ two numbers that are even or odd from }S_n\}\\ \text{and so }2 \mid \sum_{j=1}^2x_j\\ \text{So }P(1)\text{ is true.}$
By extension, it can be checked that P(0) is true as every integer is divisible by 1.
__________________________
$\text{Now, let }k\text{ be an integer for which }P(k)\text{ is true.}\\ \text{Then, for }S_k \subset \mathbb{N}, \quad |S|=2^{k+1}\\ \exists T_k \subset S_k\quad |S_k|=2^{k}\\ \text{s.t. }2^k \mid \sum_{j=1}^{2^k}x_j\quad \forall x_j\in T_k\quad (x_j\text{ distinct})\\ \text{RTP: The truth of }P(k+1)\text{ via this hypothesis}$
__________________________
$|S_{k+1}|=2^{k+2}, \quad |T_{k+1}|=2^{k+1}\\ \text{and we want }T_{k+1}\text{ chosen such that }\forall\text{ distinct }x_j\in T_{k+1} \subset S_{k+1}\\ 2^{k+1}\mid \sum_{k=0}^{2^{k+1}}x_j\\ \text{which is equivalent to}\\ \sum_{k=0}^{2^{k+1}}x_j \equiv 0 \mod 2^{k+1}$
$\text{Observe that if }x\equiv 0 \mod 2^n\\ \text{Then }x\equiv 0, 2^n \mod 2^{n+1}\\ \text{and ultimately, the former is what we are aiming for.}\\ \text{Note that }x\equiv 0 \mod 2^n\text{ is what we base our inductive hypothesis out of.}$
__________________________
$\text{Partition }S_{k+1}\text{ into four subsets of equal size, with quarters and halves denoted as such:}\\ S = \{ \dots \bullet \dots \mid \dots \bullet \dots \}\\ \text{And split the cases up}$
$\text{Case 1: Take any two quarters, and suppose the elements sum to both}\\ 0\text{ or }2^k \mod 2^{k+1}\text{, acceptable by inductive hypothesis}\\ \text{Then }0+0\equiv 0 \mod 2^{k+1}\\ \text{and }2^k+2^k=2^{k+1}\equiv 0\mod 2^{k+1}\\ \text{So take }T_{k+1}\text{ as the union of these quarters and we are done.}$
__________________________
$\text{Case 2: Now, suppose in }S_{k+1}\text{, one of the four subsets' elements sum to }0\\\text{but another sums to }2^{k}$
$\text{Suppose, without loss of generality, the sum of the first quarter's elements is }0\mod 2^{k+1}\\ \text{and the sum of the third's is }2^k \mod 2^{k+1}\\ \text{Then the diagram can be relabelled as, taken modulo }2^{k+1}\\ \{ \text{sum to 0} \bullet \dots \mid \text{sum to }2^k \bullet \dots \}$
$\text{Leaving us with the second and fourth quarters.}\\ \text{Join these quarters, then we have a subset of size }2^{k+1}\\ \text{which is disjoint from the sets made by the first and third quarters.}$
$\text{So in this pair, there exists a subset by the hypothesis that also has sum}\\ 0\text{ or }2^k \mod 2^{k-1}\\ \text{If it sums to 0, pair (union) it with the first quarter's elements.}\\ \text{If it sums to }2^k\text{, pair it with the third quarter's elements.}$
$\text{By similar calculations, it can be shown that choosing elements like this}\\ \text{guarantees a subset that's }0\mod 2^{k-1}\text{ of size }k-1\\ \text{Hence, we can define }T_{k+1}\text{in any of the above ways, so this case also holds}\\ \text{Therefore }P(k+1)\text{ is true regardless of which case we pick.}$
$\textit{So by the principle of mathematical induction, the statement holds }\forall n \in \mathbb{Z}^+$

Ali_Abbas · « **Reply #6 on:** November 01, 2016, 07:55:19 am »

I believe I may have a simpler, non-inductive proof of the result.

$\text{We wish to prove that } \forall n \in \mathbb{N}, \text{ we can always choose } 2^{n} \text{ natural} \\ \text{numbers out of a set of } 2^{n+1} \text{ of them with the property that} \\ \text{their sum is divisible by } 2^{n}. \\ \text{Fix } n \in \mathbb{N} \text{ and suppose we have a set comprising} \\ 2^{n+1} \text{ natural numbers (not necessarily distinct).} \\ \text{Their sum will always be bounded below by } 2^{n} \text{ (which can } \\ \text{be seen by taking each element equal to 1).} \\ \text{Observe that the condition that their sum is divisible by} \\ 2^{n} \text{ relies on the parities of the numbers chosen.} \\ \text{We require an even number of odds and an}\\ \text{even number of evens. Now consider that} \\ 2^{n+1} = 2 \times 2^{n}. \\ \text{The parities of the numbers can be partitioned into} \\ \text{the following cases:} \\ (1) \space 2^{n} \text{ evens, } 2^{n} \text{ odds.} \\ (2) < 2^{n} \text{ evens, } > 2^{n} \text{ odds.} \\ (3) > 2^{n} \text{ evens, } < 2^{n} \text{ odds.} \\ \text{The union of these will be all possible combinations} \\ \text{of evens and odds.} \\ \text{Since we only need to demonstrate the property of} \\ \text{existence, it suffices to select just one sample of} \\ 2^{n} \text{ numbers in each case. This is trivially done} \\ \text{as follows:} \\ \text{Case (1): Choose the } 2^{n} \text{ evens.} \\ \text{Case (2): Choose any } 2^{n} \text{ odds.} \\ \text{Case (3): Choose any } 2^{n} \text{ evens.} \\ \text{Thus, by exhaustion, the result is met.} \\ $

RuiAce · « **Reply #7 on:** November 01, 2016, 08:00:00 am »

I only thought in that direction because it said induction. Although nice seeing that exhaustion is 'somewhat' tidy, because usually it's just messy

Small technicalities:
- It is bounded below by 2ⁿ but I assumed that the elements must be distinct, so it's actually bounded below by 1+2+...+2ⁿ. This doesn't matter too much.
- That condition on the even number of odds and evens requires clarification. That is still a lemma; it's intuitive but not obvious.

Mahan · « **Reply #8 on:** November 01, 2016, 09:38:19 am »

Quote from: RuiAce on November 01, 2016, 06:28:00 am

Warning: What follows gone tremendously outside "Mathematics Extension 2" territory. Concepts here are NOT examinable and should NOT be treated as the standard of the course. Technically, not even set theory is examinable.

Disclaimer: Not all my own material. Credit shared to someone who helped me out. Which leads to query - what is the source of this question? Was it actually doable by 4U methods $\text{Let }S_{n} \subset \mathbb{N}\text{ s.t. }|S_n|=2^{n+1}\\ \text{Then, suppose }\exists T_n \subset S_n\text{ s.t. }|T_n| = 2^n$
$\text{Let }P(n)\text{ be the proposition that }\forall x_j \in T_n\quad (x_i = x_j \iff i = j)\\ 2^n \mid \sum_{j=1}^{2^n}x_j$
Note that existential quantification is assumed at the start as per the wording of the question. If universal quantification were chosen, then for n=1, take the set {1, 2, 3, 4}. Then clearly 1+2 = 3 and 3 is not divisible by 2.
$\text{Consider }P(1):\\ |S_1| = 4\text{ and }|T_1|=2\\ \text{Observe that the set }T_n\text{ must be formed such that}\\ \text{the sum of the elements in }T_n\text{ is divisible by 2.}\\ \text{Further, note that the sum of two even, or the sum of two odd numbers, is divisible by 2.}$
$\text{By the pigeonhole principle, since }|S_1|=4\\ \text{There must be }\left\lceil \frac{4}{2}\right\rceil = 2\text{ numbers in }S_1\text{ of the same parity}\\ \text{i.e. they are both odd or both even}$
$\text{Hence, take }T_n=\{\text{ two numbers that are even or odd from }S_n\}\\ \text{and so }2 \mid \sum_{j=1}^2x_j\\ \text{So }P(1)\text{ is true.}$
By extension, it can be checked that P(0) is true as every integer is divisible by 1.
__________________________
$\text{Now, let }k\text{ be an integer for which }P(k)\text{ is true.}\\ \text{Then, for }S_k \subset \mathbb{N}, \quad |S|=2^{k+1}\\ \exists T_k \subset S_k\quad |S_k|=2^{k}\\ \text{s.t. }2^k \mid \sum_{j=1}^{2^k}x_j\quad \forall x_j\in T_k\quad (x_j\text{ distinct})\\ \text{RTP: The truth of }P(k+1)\text{ via this hypothesis}$
__________________________
$|S_{k+1}|=2^{k+2}, \quad |T_{k+1}|=2^{k+1}\\ \text{and we want }T_{k+1}\text{ chosen such that }\forall\text{ distinct }x_j\in T_{k+1} \subset S_{k+1}\\ 2^{k+1}\mid \sum_{k=0}^{2^{k+1}}x_j\\ \text{which is equivalent to}\\ \sum_{k=0}^{2^{k+1}}x_j \equiv 0 \mod 2^{k+1}$
$\text{Observe that if }x\equiv 0 \mod 2^n\\ \text{Then }x\equiv 0, 2^n \mod 2^{n+1}\\ \text{and ultimately, the former is what we are aiming for.}\\ \text{Note that }x\equiv 0 \mod 2^n\text{ is what we base our inductive hypothesis out of.}$
__________________________
$\text{Partition }S_{k+1}\text{ into four subsets of equal size, with quarters and halves denoted as such:}\\ S = \{ \dots \bullet \dots \mid \dots \bullet \dots \}\\ \text{And split the cases up}$
$\text{Case 1: Take any two quarters, and suppose the elements sum to both}\\ 0\text{ or }2^k \mod 2^{k+1}\text{, acceptable by inductive hypothesis}\\ \text{Then }0+0\equiv 0 \mod 2^{k+1}\\ \text{and }2^k+2^k=2^{k+1}\equiv 0\mod 2^{k+1}\\ \text{So take }T_{k+1}\text{ as the union of these quarters and we are done.}$
__________________________
$\text{Case 2: Now, suppose in }S_{k+1}\text{, one of the four subsets' elements sum to }0\\\text{but another sums to }2^{k}$
$\text{Suppose, without loss of generality, the sum of the first quarter's elements is }0\mod 2^{k+1}\\ \text{and the sum of the third's is }2^k \mod 2^{k+1}\\ \text{Then the diagram can be relabelled as, taken modulo }2^{k+1}\\ \{ \text{sum to 0} \bullet \dots \mid \text{sum to }2^k \bullet \dots \}$
$\text{Leaving us with the second and fourth quarters.}\\ \text{Join these quarters, then we have a subset of size }2^{k+1}\\ \text{which is disjoint from the sets made by the first and third quarters.}$
$\text{So in this pair, there exists a subset by the hypothesis that also has sum}\\ 0\text{ or }2^k \mod 2^{k-1}\\ \text{If it sums to 0, pair (union) it with the first quarter's elements.}\\ \text{If it sums to }2^k\text{, pair it with the third quarter's elements.}$
$\text{By similar calculations, it can be shown that choosing elements like this}\\ \text{guarantees a subset that's }0\mod 2^{k-1}\text{ of size }k-1\\ \text{Hence, we can define }T_{k+1}\text{in any of the above ways, so this case also holds}\\ \text{Therefore }P(k+1)\text{ is true regardless of which case we pick.}$
$\textit{So by the principle of mathematical induction, the statement holds }\forall n \in \mathbb{Z}^+$

Thank you RuiAce, that was an interesting proof but I think we can come up with a more simple and a proof of at extension2 level.The interesting thing about this proof is we use induction hypothesis multiple times whereas in usual induction proof we use induction hypothesis only once.Also on the prod you don't need the distinction assumption.
Here is the proof:

RuiAce · « **Reply #9 on:** November 01, 2016, 09:54:53 am »

Whilst I don't deny the course has been made easier, neither of the proofs provided are to within reasonable bounds of the current Extension 2 level, especially with how the inductive hypothesis must be applied more than once.

Because expecting an Extension 2 student to think that deeply into pure mathematics is stretching too far. The necessity of considering the elements in such a way, despite being one of the easiest things to teach, is not something that one is expected to know.

As for simplicity though, I'd say that your answer is indeed simpler

(We could really add a beyond 4U section of this forum but I didn't bring it up cause I didn't see enough value in it yet - forum still needs popularity for that.)
_______________________________________________
$\text{However, if the elements of }T_{k+1}\text{ are allowed to be the same element iterated}\\ \text{Then the sum becomes something not bound by strict conditions anymore.}\\ \text{Because we can take ANY }x_j \in T_{k+1}\text{ and add itself }2^{k+1}\text{times.}$
$\text{Which is why in set theory, an iterated element is classified as the same element.}\\ \text{In such a way, the cardinality of the set remains defined as well.}$

Also, I still wish to ask for my friend. What is the source of this question?

Mahan · « **Reply #10 on:** November 01, 2016, 10:25:00 am »

Quote from: RuiAce on November 01, 2016, 09:54:53 am

Whilst I don't deny the course has been made easier, neither of the proofs provided are to within reasonable bounds of the current Extension 2 level, especially with how the inductive hypothesis must be applied more than once.

Because expecting an Extension 2 student to think that deeply into pure mathematics is stretching too far. The necessity of considering the elements in such a way, despite being one of the easiest things to teach, is not something that one is expected to know.

As for simplicity though, I'd say that your answer is indeed simpler

(We could really add a beyond 4U section of this forum but I didn't bring it up cause I didn't see enough value in it yet - forum still needs popularity for that.)
_______________________________________________
$\text{However, if the elements of }T_{k+1}\text{ are allowed to be the same element iterated}\\ \text{Then the sum becomes something not bound by strict conditions anymore.}\\ \text{Because we can take ANY }x_j \in T_{k+1}\text{ and add itself }2^{k+1}\text{times.}$
$\text{Which is why in set theory, an iterated element is classified as the same element.}\\ \text{In such a way, the cardinality of the set remains defined as well.}$

Also, I still wish to ask for my friend. What is the source of this question?

I agree that the level of the question is higher than what we should expect from an average Extension2 student but I think by exposing students to these simple but interesting ideas, we will open their minds and will give them some problem solving skills that might be useful in different types of questions.
But I agree with you.

About the repeated elements, Although you are right about undefined cardinality of the sets if we choose multiple elements, This is a restriction you imposed on the question by using set theory. In my proof I avoided using set theory, although I used the word set, I should've used collection instead. In the question there is no mention of distinct elements.
the book is an introduction to IMO competition but unfortunately it is in another language, I chose that question carefully to make sure the question is easy and doable for ext2 students and at the same time it uses a new idea that most students have not seen before.
If you are interested I can cite the book, but I don't think it is gonna be useful.

RuiAce · « **Reply #11 on:** November 01, 2016, 10:32:07 am »

Quote from: Mahan on November 01, 2016, 10:25:00 am

I agree that the level of the question is higher than what we should expect from an average Extension2 student but I think by exposing students to these simple but interesting ideas, we will open their minds and will give them some problem solving skills that might be useful in different types of questions.
But I agree with you.

About the repeated elements, Although you are right about undefined cardinality of the sets if we choose multiple elements, This is a restriction you imposed on the question by using set theory. In my proof I avoided using set theory, although I used the word set, I should've used collection instead. In the question there is no mention of distinct elements.
the book is an introduction to IMO competition but unfortunately it is in another language, I chose that question carefully to make sure the question is easy and doable for ext2 students and at the same time it uses a new idea that most students have not seen before.
If you are interested I can cite the book, but I don't think it is gonna be useful.

Was all necessary, cheers (y) @source

Whilst it's a shame that most people are just there in 4U because they're good at maths and don't necessarily have a passion for it, it's still something to consider. It's quite unfortunate how these things are often glanced at and then ignored.

Mahan · « **Reply #12 on:** December 11, 2016, 09:24:19 pm »

Well, it's been a while since I have posted an induction question. A few days ago I came across another interesting induction question.

Suppose $a_{0} = 1, a_{1} = 2$ and for $n \geq 1$ we have

$a_{n+1} = a_{n} + \frac{a_{n-1}}{1 + a^{2}_{n-1}}$

then prove by induction, for every $n \geq 0$

$\sqrt{2n+1} \leq a_{n} < \sqrt{3n+2}$

Search the forums now!

We have moved!

Author Topic: Interesting induction questions (Read 6235 times) Tweet Share

Mahan

Interesting induction questions

RuiAce

Re: Interesting induction questions

Mahan

Re: Interesting induction questions

RuiAce

Re: Interesting induction questions

Mahan

Re: Interesting induction questions

RuiAce

Re: Interesting induction questions

Ali_Abbas

Re: Interesting induction questions

RuiAce

Re: Interesting induction questions

Mahan

Re: Interesting induction questions

RuiAce

Re: Interesting induction questions

Mahan

Re: Interesting induction questions

RuiAce

Re: Interesting induction questions

Mahan

Re: Interesting induction questions

Recent Posts

User:
Password: