Problem 50 - Discrete Mathematics with Applications

Question

The \(n\) th term \(b_{n}\) of a number sequence is defined by \(b_{n}=\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta},\) where \(\alpha=(1+\sqrt{5}) / 2\) and \(\beta=(1-\sqrt{5}) / 2\) are solutions of the equation \(x^{2}=x+1\) Verify each. $$b_{n}=b_{n-1}+b_{n-2}, n \geq 3$$

Step-by-Step Solution

Answer

The short answer is: To verify the given property, \(b_n = b_{n-1} + b_{n-2}\), we substitute the values of \(\alpha\) and \(\beta\) into the formula for \(b_n\), \(b_{n-1}\), and \(b_{n-2}\) and simplify the expressions. After adding \(b_{n-1}\) and \(b_{n-2}\) and using the equation \(x^2 = x + 1\) for \(\alpha\) and \(\beta\), we are able to simplify the expression to show that \(b_n = b_{n-1} + b_{n-2}\) for \(n \geq 3\).

Step 1: Write the formulas for \(b_n\), \(b_{n-1}\) and \(b_{n-2}\)

: Given \(b_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}\), we can write the formulas for \(b_{n-1}\) and \(b_{n-2}\) as follows: \[b_{n-1} = \frac{\alpha^{n-1} - \beta^{n-1}}{\alpha - \beta}\] \[b_{n-2} = \frac{\alpha^{n-2} - \beta^{n-2}}{\alpha - \beta}\]

Step 2: Add \(b_{n-1}\) and \(b_{n-2}\)

: Now, we will add \(b_{n-1}\) and \(b_{n-2}\): \[b_{n-1} + b_{n-2} = \frac{\alpha^{n-1} - \beta^{n-1} + \alpha^{n-2} - \beta^{n-2}}{\alpha - \beta}\]

Step 3: Factor out the terms

: Factor out \(\alpha^{n-2}\) and \(\beta^{n-2}\) terms from the numerator: \[b_{n-1} + b_{n-2} = \frac{\alpha^{n-2}(\alpha - 1) - \beta^{n-2}(\beta - 1)}{\alpha - \beta}\]

Step 4: Use the equation \(x^2 = x + 1\) for \(\alpha\) and \(\beta\)

: Since \(\alpha\) and \(\beta\) are solutions of the equation \(x^2 = x + 1\): \[\alpha^2 = \alpha + 1\] \[\beta^2 = \beta + 1\] Now replace \((\alpha - 1)\) with \(\alpha^2\) and \((\beta - 1)\) with \(\beta^2\) in the expression for \(b_{n-1} + b_{n-2}\): \[b_{n-1} + b_{n-2} = \frac{\alpha^{n-2}\alpha^2 - \beta^{n-2}\beta^2}{\alpha - \beta}\]

Step 5: Simplify the expression

: Now, simplify the expression by combining the powers of \(\alpha\) and \(\beta\): \[b_{n-1} + b_{n-2} = \frac{\alpha^n - \beta^n}{\alpha - \beta}\] Recall that this is the formula for \(b_n\): \[b_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}\] Hence, we have shown that \(b_n = b_{n-1} + b_{n-2}\) for \(n \geq 3\).

Key Concepts

Recurrence Relations

Recurrence relations are mathematical equations that express the terms of a sequence based on previous terms. This means that in a number sequence, to find the next number, you often rely on deriving it from a fixed number of prior numbers in the pattern.
In this exercise, the recurrence relation given is: \( b_n = b_{n-1} + b_{n-2} \) for \( n \geq 3 \). This is typical of a Fibonacci type sequence where each term is a sum of its two preceding terms. Understanding this pattern helps solve sequences step-by-step by developing them iteratively, using previously known values.
Recurrence relations can be

• Linear, where the relation is a linear equation of the preceding terms.
• Homogeneous, where the relation is set to zero as seen here, since \( b_n - b_{n-1} - b_{n-2} = 0 \).
• Non-homogeneous, where additional terms or constants appear in the relation.
• First-order, second-order, etc., depending on how many preceding terms are used.

Mastering recurrence relations is crucial in fields like computer science and mathematics, where they are widely used in algorithms and numerical methods.

Golden Ratio

The Golden Ratio, often denoted by the Greek letter \( \phi \) (phi), is a mathematical constant approximately equal to 1.6180339887. It is closely associated with the Fibonacci sequence and has unique properties thatdescribe a roughly 1:1.618 ratio.
In mathematics, when two numbers \( \alpha \) and \( \beta \) are solutions to the equation \( x^2 = x + 1 \), they are linked to the Golden Ratio. Here, \( \alpha = \frac{1+\sqrt{5}}{2} \) and \( \beta = \frac{1-\sqrt{5}}{2} \) are precisely these solutions. This relation appears in many natural phenomena, art, and architecture, emphasizing aesthetics andproportional beauty.
In this exercise specific context, the process of manipulating these algebraic expressions through the Golden Ratio quantities helps verify the validity of the given recurrence relation for the sequence.

Mathematical Induction

Mathematical Induction is a powerful proof method used in mathematics to demonstrate the truth of an infinite number of cases. It is often employed for statements or propositions about integers.
Induction works in two steps:

• Base Case: Verify that the statement holds for the initial value, often \( n=1 \).
• Inductive Step: Assume the statement is true for \( n = k \) (Inductive Hypothesis), then prove it holds for \( n = k+1 \).

This method establishes the universal truth by building a domino effect from a known starting point. In the context of the exercise, while induction itself is not explicitly used, you verify in a similar incremental fashion that each term of the sequence fits the recurrence relation from step to step. Understanding induction helps in mastering sequence-based problems, particularly those involving recurrence relations.