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.