0

NOTE: This MUST be done with simple induction

I'm currently stuck on properly proving induction on a set when floor is involved.

I have made up a question to illustrate the issue, it may not be a great question but hopefully you can see where I'm stuck.

For a set S of elements 0 to n, and a function A that extracts all the elements of a set which, when modded by 3, equals 2.

Example:

$$X = \{0, 1, 2, 3, 4, 5, 6, 7, 8\}$$

Let function A take a set and remove every element except the ones where 'element mod 3 = 2'

$$ A(X) = \{2, 5, 8\}$$

Show that any set of size n passed through function A will result in the output of a set with a size of $$\left \lfloor{\frac{n}{3}}\right \rfloor$$

For simple induction, we prove the base case, this is trivial.

The part I'm stuck with is when you are trying to show that $$P(n) \implies P(n+1) $$

It was easy for when n = 3k + 1, since n + 1 becomes an element not filtered out, and you can (with some manipulation) show that the following works: $$\left \lfloor{\frac{n + 1}{3}}\right \rfloor$$

However, where I am stuck is showing that for n = 3k, n + 1 will follow. Since 3k is removed, and 3k + 1 is removed, I don't know how I'm supposed to get to floor(n/3) since the set size will not increase. Intuitively this makes sense, but trying to prove it via induction has me confused to properly do it.

  • Do I just say floor(n/3) = floor(n=1 / 3) for obvious reasons?

  • Do I equate the two above and just say "works for n = 3k and n = 3k + 2" with cases?\

  • Am I supposed to show that 3k implies that 3k+1 implies 3k+2 works, and therefore it repeats for all N?

You must assume that the reader has to be shown rigorously that simple induction holds.

You also may not use complete induction.

Water
  • 183
  • You don't need induction for this. There are exactly $\lfloor n/3\rfloor$ integers that are $\equiv2\pmod3$ between $1$ and $n.$ If you need to use induction then don't listen to me. – CIJ Sep 24 '15 at 05:06
  • @C.I.J. I am forced to use induction sadly, I will edit the post to reflect this since I didn't state it. – Water Sep 24 '15 at 05:07
  • My bad, this is not true since the number of integers between $0$ and $11$ that are $\equiv2\pmod3$ is $4\neq\lfloor 11/3\rfloor=3.$ – CIJ Sep 24 '15 at 05:12
  • Are you sure the statement you want to prove holds? It doesn't seem to apply in your example, where the size of your set is 3, which is more than 2. I believe you should replace n/3 with (n+1)/3 for the expression to be valid. – RavenclawPrefect Sep 24 '15 at 05:21
  • That one cannot use complete induction and must use simple induction is a peculiar joke, since every complete induction proof can be mechanically transformed into a simple induction proof. – André Nicolas Sep 24 '15 at 05:21
  • @AndréNicolas Ok how would you solve it with complete induction then? – Water Sep 24 '15 at 11:42
  • @RavenclawPrefect If the set size is 3, {0, 1, 2}, then floor(3/3) = floor(1) = 1, which is the size of {2}. Did I miss something? – Water Sep 24 '15 at 11:44
  • In this case we can use $3$ separate inductions and show that from $n=3k$ we can get $n=3k+3$, from $n=3k+1$ we can get $n=3k+3+1$, from $n=3k+2$ we can get n=3k+3+2. If we want to do it in one induction then the statement to prove is "for all $i$ the floor function stuff holds for any $3k+i$." The complete induction version is similar, do base cases 1,2,3, induction step goes from true for all $k\lt n$ to true for $n$ by looking at $n-3$. – André Nicolas Sep 24 '15 at 13:58
  • @Walter I was referring to the size of {2, 5, 8} in the example. Sorry for any ambiguity. – RavenclawPrefect Sep 25 '15 at 01:38

0 Answers0