Problem 53 - Discrete Mathematics with Applications

Question

Prove each, where \(x \in \mathbb{R}\) and \(n \in \mathbf{Z}\) $$\left\lfloor\frac{n}{2}\right\rfloor=\frac{n-1}{2} \text { if } n \text { is odd }$$

Step-by-Step Solution

Answer

To prove that when \(n\) is odd, \(\left\lfloor\frac{n}{2}\right\rfloor=\frac{n-1}{2}\), we first represent odd integers as \(n=2k+1\), where \(k\) is an integer. We then divide \(n\) by 2: \(\frac{n}{2}=\frac{2k+1}{2} = k+\frac{1}{2}\) Applying the floor function: \[\left\lfloor\frac{n}{2}\right\rfloor = \left\lfloor k+\frac{1}{2}\right\rfloor = k\] Finally, we substitute back \(n=2k+1\): \[\left\lfloor\frac{n}{2}\right\rfloor = k = \frac{(2k+1)-1}{2} = \frac{n-1}{2}\] Hence, we have proved the statement for \(n\) being odd.

Step 1: Understanding the Floor Function

The floor function denoted by \(\lfloor x \rfloor\) returns the greatest integer less than or equal to \(x\). For example, \(\lfloor 5.3 \rfloor = 5\), \(\lfloor -3.7 \rfloor = -4\), and \(\lfloor 10 \rfloor =10\).

Step 2: Understanding Even and Odd Integers

An integer \(n\) is called odd if it can be expressed in the form \(n = 2k + 1\), where \(k\) is also an integer. On the other hand, an integer is called even if it can be expressed in the form \(n = 2k\), where \(k\) is an integer.

Step 3: Proof: n is Odd

Now let’s assume that \(n\) is an odd integer. This means that there exists an integer \(k\) such that \(n = 2k + 1\).

Step 4: Divide n by 2

Let's divide \(n\) by 2: \[\frac{n}{2} = \frac{2k + 1}{2}\]

Step 5: Applying the floor function to n divided by 2

Now we apply the floor function: \[\left\lfloor\frac{n}{2}\right\rfloor = \left\lfloor\frac{2k + 1}{2}\right\rfloor\] Since \(k\) is an integer, \(2k\) is an even number. Thus, \(\frac{2k + 1}{2} = k + \frac{1}{2}\), where \(k\) is an integer.

Step 6: Apply the floor function

The floor function of \(k + \frac{1}{2}\) would be the greatest integer less than or equal to \(k + \frac{1}{2}\), which is equal to \(k\). So, we have: \[\left\lfloor\frac{n}{2}\right\rfloor = k\]

Step 7: Substitute n

Now, we substitute the value of \(n = 2k + 1\): \[\left\lfloor\frac{n}{2}\right\rfloor = \frac{(2k+1)-1}{2}\]

Step 8: Final Expression

Therefore, we get: \[\left\lfloor\frac{n}{2}\right\rfloor = \frac{n-1}{2}\] Hence, we have proved the statement for any odd integer \(n\).

Key Concepts

Odd Integers

An odd integer is a number in the form of \( n = 2k + 1 \), where \( k \) is an integer. This representation is essential because it helps us identify and work with odd numbers in mathematical proofs.
Why does adding 1 to an even number (\( 2k \)) make it odd? The answer lies in the properties of numbers. For any integer \( k \), \( 2k \) generates all even numbers. Adding 1 to any even number skips to the closest odd integer.
Here are some examples:

• If \( k = 0 \), then \( n = 2(0) + 1 = 1 \). 1 is odd.
• If \( k = 3 \), then \( n = 2(3) + 1 = 7 \). 7 is odd.
• If \( k = -1 \), then \( n = 2(-1) + 1 = -1 \). -1 is odd.

Odd numbers, thus, always follow this pattern, making them crucial in many mathematical contexts like proofs and division properties of integers.

Proofs in Mathematics

Proofs are the backbone of mathematics, providing a logical sequence to validate statements. Let's delve into how they apply to the concept you are working through. In this case, the statement is turning a description of an odd integer into an expression involving the floor function so that it meets the requirement \( \left\lfloor\frac{n}{2}\right\rfloor = \frac{n-1}{2} \).
Each step builds upon the previous one:

• Step 3 asserts \( n = 2k + 1 \) for odd integers.
• Step 4 divides this by 2, yielding \( \frac{n}{2} = k + \frac{1}{2} \).
• Step 5 applies the floor function on \( \frac{n}{2} \), recognizing it as \( k \) since the floor function captures the greatest integer below the decimal.

Proofs offer rigor. They tighten our understanding and ensure there are no gaps. Each step adheres to logical progression. Proofs lay the groundwork by arguing clearly and systematically until the desired conclusion is reached.

Division Properties of Integers

Division of integers is crucial for understanding how numbers relate, especially with the floor function involved. When dividing any integer \( n \) by 2:

• If \( n \) is even, \( n = 2k \), dividing gives \( \frac{n}{2} = k \).
• If \( n \) is odd, \( n = 2k + 1 \), the quotient is \( \frac{n}{2} = k + \frac{1}{2} \).

Understanding the impact of the floor function here is essential. When we apply the floor function to the expression \( k + \frac{1}{2} \), it removes the fraction and considers the greatest whole number below it, returning \( k \).
This division and floor operation interplay illustrates why for odd integers, the equation \( \left\lfloor\frac{n}{2}\right\rfloor = \frac{n-1}{2} \) holds true. It's all about recognizing how dividing an odd number by 2 creates a fractional part that the floor function eventually disregards, securing the algebraic identity required for the proof.