Shoutbox

Hi,

I have a math question that I'm having trouble proving




I know it works for a few integers because I've tested it, but what I'm having problems with is proving that it works for all integers


Could anyone lend a hand and explain how i would prove this? (I'm assuming with proof by induction, but I suck at working out the inductive step )

i dunno if im missing something, but i dont see how would that be true at all O_o

what integers did you try?

Anyway, yeah, induction is the way to go for such kind of problems

quote:

---

Originally posted by Chrono
i dunno if im missing something, but i dont see how would that be true at all O_o

what integers did you try?

Anyway, yeah, induction is the way to go for such kind of problems

---

works for 1, 99, -10

1/2 + 2/2 != 1

O_o

floor(1/2) = 0, floor (2/2) = 1, 0+1 = 1

bah sorry, i thought those where regular parenthesis My mistake

Edit:
Ok it's been a few years already since i solved these kind of problems for the last time, so i dunno if it's right

It works for 0:

floor(0) + floor(1/2) = 0

Now let's say it works for n

floor(n/2) + floor((n+1)/2) = n

then we can add 1

floor(n/2) + floor((n+1)/2) +1 = n+1

floor((n+2)/2) + floor((n+1)/2) = n+1

floor(((n+1)+1)/2) + floor((n+1)/2) = n+1

tadda

Ok, now I'm not sure the norm for calculating for all integers (usually induction questions ask for all positive XOR negative integers). But this is how I would do it:

Prove true for n = 0

LHS:
= floor(0/2) + floor[(0+1)/2]
= floor(0) + floor(0.5)
= 0

RHS:
= n
= 0

LHS = RHS, therefore true for n = 0


Now, assume true for n = k
i.e.
floor(k/2) + floor[(k+1)/2] = k
NOTE: This rearranges to floor(k/2) = k - floor[(k+1)/2] used later in our proof.

Prove true for n = k + 1
i.e. Prove floor[(k+1)/2] + floor[(k+2)/2] = k + 1
LHS:
= floor[(k+1)/2] + floor[(k+2)/2]
= floor[(k+1)/2] + floor(k/2 + 2/2)
= floor[(k+1)/2] + floor(k/2 + 1)
= floor[(k+1)/2] + floor(k/2) + 1
= floor[(k+1)/2] + k - floor[(k+1)/2] + 1  <------- we assumed that it's true for n = k so sub in the assumption here (the bolded part above)
= k + 1
= RHS

Therefore if it is true for n = k, then it is also true for n = k + 1
Therefore since it is true for n = 0, it must also be true for n = 0 + 1 = 1, and since it is true for n = 1 it must also be true for n = 2, and so on for all positive integers n >= 0.

Now we've proven it for positive integers (and 0), we want to prove it for negative integers too (so as to include all possible integers n as requested in the question)

Therefore:
Prove true for n = k - 1
i.e. Prove floor[(k-1)/2] + floor(k/2) = k - 1
LHS:
= floor[(k-1)/2] + floor(k/2)
= floor[(k-1)/2] + k - floor[(k+1)/2]   <---- we just substituted in our assumption again for floor(k/2)
= k + floor[(k-1)/2] - floor[(k+1)/2]
= k + floor(k/2 - 1/2) - floor(k/2 + 1/2)

        DETOUR:
        Now, we know that k is an integer, if it is an odd integer then k/2 would be: x + 1/2 where x is an integer (eg. 5/2 = 2 + 1/2)
        floor(x + 1/2 - 1/2) = floor(x ) = x
        floor(x + 1/2 + 1/2) = floor(x+1) = x + 1
        Therefore floor(x + 1/2 - 1/2) - floor(x + 1/2 + 1/2) = -1

        If k were an even integer, then k/2 would be: x where x is an integer (eg. 4/2 = 2)
        floor(x - 1/2) = x - 1
        floor(x + 1/2) = x
        Therefore floor(x - 1/2) - floor(x + 1/2) = -1

        So for any integer k, floor(k/2 - 1/2) - floor(k/2 + 1/2) = -1

        Now back to our proof:

= k + floor(k/2 - 1/2) - floor(k/2 + 1/2)
= k - 1
= RHS

There if it is true for n = k, then it is also true for n = k - 1
Therefore since it is true for n = 0, it must also be true for n = 0 - 1 = -1, and since it is true for n = -1 it must also be true for n = -2, and so on for all negative integers n < 0

Now we've proven it for negative integers as well as the positive integers (and 0) earlier.
Therefore, it is true for all integers n (positive, negative, 0)

quote:

---

Originally posted by Chrono
bah sorry, i thought those where regular parenthesis My mistake

Edit:
Ok it's been a few years already since i solved these kind of problems for the last time, so i dunno if it's right

It works for 0:

floor(0) + floor(1/2) = 0

Now let's say it works for n

floor(n/2) + floor((n+1)/2) = n

then we can add 1

floor(n/2) + floor((n+1)/2) +1 = n+1

floor((n+2)/2) + floor((n+1)/2) = n+1

floor(((n+1)+1)/2) + floor((n+1)/2) = n+1

tadda

---

You suck at induction

...
then we can add 1

floor(n+1/2) + floor(((n+1)+1)/2) = n+1
floor((n+1)/2) + floor((n+2)/2) = n+1
floor((n+1)/2) + floor(n/2 + 1) = n+1

floor(a + 1) = floor + 1 as 1 is an integer

floor((n+1)/2) + floor(n/2) + 1 = n+1
floor(n/2) + floor((n+1)/2) + 1 = n+1

substitue n from (1)
n+1 = n+1
therefor true for n+1 for all n
take n=0 (as proven), then n=1 is also true, then n=2 is also true and so on and so forth

similarly the same can be proven for -1 using the same methods and thus applies from n=0, hence this is proven where n is any integer

EDIT: Volv gets full marks...

Wow Volv. You left me ecstatic.

I think it would be possible to prove it logically rather than through induction as well:

Prove floor(n/2) + floor(n/2 + 1/2) = n

LHS:
If n is even then n/2 = x where x is a whole number (integer)
Therefore floor(n/2) + floor(n/2 + 1/2)
= floor(x) + floor(x + 1/2)
= x + x
= 2x
= n
= RHS

If n is odd then n/2 = x + 1/2 where x is a whole number (integer)
Therefore floor(n/2) + floor(n/2 + 1/2)
= floor(x + 1/2) + floor(x + 1/2 + 1/2)
= x + x + 1
= 2x + 1
= 2(x + 1/2)
= n
= RHS

Therefore for any odd or even numbers it will be true (i.e. true for all integers). You can say that 0 is included under even numbers or prove it manually.

I think this is probably a better proof than induction considering that my proof for negative numbers by induction required this sort of logical analysis anyway. I guess it depends on the topic you're studying and whether they've specified a certain method.