0
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – CIJ
    Sep 24 '15 at 5:06
  • $\begingroup$ @C.I.J. I am forced to use induction sadly, I will edit the post to reflect this since I didn't state it. $\endgroup$
    – Water
    Sep 24 '15 at 5:07
  • $\begingroup$ 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.$ $\endgroup$
    – CIJ
    Sep 24 '15 at 5:12
  • $\begingroup$ 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. $\endgroup$ Sep 24 '15 at 5:21
  • $\begingroup$ 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. $\endgroup$ Sep 24 '15 at 5:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.