Problem 28 - Discrete Mathematics with Applications

Question

Show that $$\mathrm{a}_{n}=\left\\{\begin{array}{ll}{1} & {\text { if } n=1} \\\ {a_{n-1}+n / 2} & {\text { if } n>1 \text { and even }} \\ {a_{n-1}+(n+1) / 2} & {\text { if } n>1 \text { and odd }}\end{array}\right.$$

Step-by-Step Solution

Answer

Using the principle of mathematical induction, we have shown that the given formula for \(\mathrm{a}_{n}\) holds true for all positive integer values of \(n\). The base case is satisfied for \(n=1\), and we established the induction hypothesis for a positive integer \(k\). We then proved the formula for the cases when \(k+1\) is even and odd, thus completing the induction proof.

Step 1: Base Case

Let's check the base case when \(n=1\). The given formula states that \(\mathrm{a}_{1}=1\), which is true by definition. So, the base case is satisfied.

Step 2: Induction Hypothesis

Now suppose that the formula holds true for some positive integer \(k\), meaning: \[\mathrm{a}_{k}=\left\\\begin{array}{ll}{1} & {\text { if } k=1} \\\ {a_{k-1}+k / 2} & {\text { if } k>1 \text { and even }} \\\ {a_{k-1}+(k+1) / 2} & {\text { if } k>1 \text { and odd }}\end{array}\right.\]

Step 3: Inductive Step (Even case)

We must prove that the formula is true for \(k+1\) if \(k+1\) is even. Using the induction hypothesis, we have that \(\mathrm{a}_{k+1} = a_k + \frac{k+1}{2}\), so: \[\mathrm{a}_{k+1} = \left(a_{k-1} + \frac{k}{2}\right) + \frac{k+1}{2}\] Now, if \(k+1\) is even, then \(k = 2m-1\) for some positive integer \(m\). Therefore, we have: \[\mathrm{a}_{k+1} = \left(a_{k-1} + \frac{2m-1}{2}\right) + \frac{2m}{2}\] \[=\left(a_{k-1}+\frac{2m-1+2m}{2}\right)=a_{k-1}+m\] Hence, the formula holds true for the even case.

Step 4: Inductive Step (Odd case)

We must now prove that the formula is true for \(k+1\) if \(k+1\) is odd. Using the induction hypothesis for an odd \(k\), we have that \(\mathrm{a}_{k+1} = a_k + \frac{k+1+1}{2}\), so: \[\mathrm{a}_{k+1} = \left(a_{k-1} + \frac{k+2}{2}\right) + \frac{k+2}{2}\] Now, if \(k+1\) is odd, then \(k = 2m\) for some positive integer \(m\). Therefore, we have: \[\mathrm{a}_{k+1} = \left(a_{k-1} + \frac{2m+2}{2}\right) + \frac{2m+2}{2}\] \[=\left(a_{k-1}+\frac{2m+2+2m+2}{2}\right)=a_{k-1}+(m+1)\] Hence, the formula holds true for the odd case.

Step 5: Conclusion

By the principle of mathematical induction, we have shown that the given formula for \(\mathrm{a}_{n}\) holds true for all positive integer values of \(n\).

Key Concepts

Understanding the Base Case

In the realm of mathematical induction, the base case serves as the crucial starting point of our proof. Think of it as the foundation of a building; without a strong base, the entire structure can topple. In the exercise, when we have to show that a sequence given by a certain formula is true for all natural numbers, we first focus on the smallest number in our domain, typically 1.

For our specific problem, the base case is when the sequence \(a_n\) begins with \(n=1\). The formula states, quite simply, that \(a_1 = 1\), and by checking this we can confirm it holds true. Verifying the base case may seem like a small step, but its role is undeniably significant. It's the first checkmark on our list that we need before we can confidently march on to the next phase: the induction hypothesis.

Formulating the Induction Hypothesis

Moving from the base case, we then establish the induction hypothesis. This is where we assume that our formula works for a certain case. Here's a helpful analogy: if you're climbing a ladder, the induction hypothesis is akin to standing firmly on one rung and reaching out to prove you can safely step onto the next.

In our exercise, we hypothesize that our sequence formula is true for an arbitrary positive integer \(k\): that is, \(a_k\) obeys the given recursive formula whether \(k\) is even or odd. This is a crucial step—it's not proving anything about the entire sequence yet, but rather setting up a 'domino effect' for our proof. We can't prove every single case individually, so we assume one case with the intention of showing that if this one case is true, then the next one will follow suit.

Executing the Inductive Step

The inductive step is where the magic of induction truly unfolds. After setting up our assumption in the induction hypothesis, we must now show that the formula also holds for the next integer, \(k+1\). This part of the process is like proving you can actually step onto the next rung of the ladder, having presumed that the one you're standing on is stable.

In the context of our sequence, we tackle this by considering two scenarios—when \(k+1\) is even, and when it's odd—since the formula differs based on the parity of \(n\). For each case, we take our induction hypothesis as a given and manipulate it to show that the formula holds for \(a_{k+1}\), hence proving our assumption leads to a true statement for the next element. Once we succeed in this, the 'dominoes start to fall', and we can conclude through the principle of mathematical induction that the sequence formula is indeed true for every positive integer.