Question

Solve \(T(n)=T(n-1)+n\) for \(n \geq 2\) with \(T(1)=1\).

Short answer

The solution is \(T(n) = \frac{n(n+1)}{2}\), a triangular number formula.

Step-by-step solution

Understand the Problem

We have a recursive formula: \(T(n) = T(n-1) + n\), which means that the function value at \(n\) is the function value at \(n-1\) plus \(n\). We also have a base case given by \(T(1) = 1\). Our goal is to find a general expression for \(T(n)\).

Build the Recurrence

Start from the base case \(T(1) = 1\). Let's calculate the next few terms to look for a pattern:- \(T(2) = T(1) + 2 = 1 + 2 = 3\)- \(T(3) = T(2) + 3 = 3 + 3 = 6\)- \(T(4) = T(3) + 4 = 6 + 4 = 10\)Notice that these results (1, 3, 6, 10) are triangular numbers.

Identify the Pattern

The numbers calculated in Step 2 seem to follow the pattern of triangular numbers, which can be expressed with the formula \(T(n) = \frac{n(n+1)}{2}\). Triangular numbers are sums of consecutive integers: 1, 1+2, 1+2+3, etc.

Prove by Mathematical Induction

Base Case: For \(n = 1\), the formula gives \(T(1) = \frac{1 \times (1+1)}{2} = 1\), which matches the initial condition.Induction Hypothesis: Assume for some \(k \geq 1\), \(T(k) = \frac{k(k+1)}{2}\).Inductive Step: Prove \(T(k+1) = \frac{(k+1)(k+2)}{2}\).Starting from the recursive definition: \(T(k+1) = T(k) + (k+1)\).Using the induction hypothesis: \(T(k+1) = \frac{k(k+1)}{2} + (k+1)\).Factor \(k+1\) out: \(T(k+1) = (k+1)\left(\frac{k}{2} + 1\right) = (k+1)\left(\frac{k+2}{2}\right)\).This simplifies to \(T(k+1) = \frac{(k+1)(k+2)}{2}\), completing the induction.

Key concepts

Mathematical Induction

Mathematical induction is a powerful technique used to prove statements about natural numbers. It involves a base case and an inductive step.

• Base Case: You start by proving the statement is true for the initial value, often starting at 1. In our exercise, the base case checks if the triangular number formula gives the correct result for \(n=1\), which it does.\( T(1) = \frac{1(1+1)}{2} = 1 \).
• Inductive Step: You assume the statement is true for some arbitrary natural number \(k\), and then show it's true for \(k+1\). This is like proving a domino effect: if one number works, the next one will too.

In the induction process from the solution, we assumed \(T(k) = \frac{k(k+1)}{2}\) holds. Then, using the recursive relation, added \((k+1)\) to find \(T(k+1)\). It simplifies beautifully to \(\frac{(k+1)(k+2)}{2}\), showing the pattern holds for all \(n\).
This method ensures that the formula for triangular numbers is correct for any positive integer \(n\). It's a comprehensive way to deal with proofs in mathematics, making it indispensable in areas involving sequences and series.

Triangular Numbers

Triangular numbers are figures that represent objects arranged in an equilateral triangle. If you imagine stacking coins, each row having one more coin than the last, you get a triangular number. These are numbers like 1, 3, 6, 10, where each can be expressed as the sum of a sequence of consecutive positive integers, starting from 1.

The general formula to find the \(n\)-th triangular number is given by: \[ T(n) = \frac{n(n+1)}{2} \]This formula shows that triangular numbers grow as the sum of integers up to \(n\). The derivation comes from considering the sequence of additions involved in each number.

• The first triangular number is just 1.
• The second is \(1 + 2 = 3\).
• The third is \(1 + 2 + 3 = 6\).
• And the pattern continues indefinitely.

The elegance of triangular numbers is not just in their arithmetic, but also their geometry, reflecting symmetry and the beginning of understanding number patterns, which are crucial in combinatorics and number theory.

Recursive Functions

Recursive functions define sequences where each term is defined based on previous terms, with at least one base case. This recursive nature allows complex problems to be solved in smaller, more manageable chunks.

In the given problem, we see a recursive formula: \[ T(n) = T(n-1) + n \]This explains that each term \(T(n)\) is the result of the previous term \(T(n-1)\) plus \(n\). Having a base case \( T(1) = 1 \) ensures the sequence starts properly.

• Recursive definitions are common in computer science for algorithms like sorting, searching, and dynamic programming where problems are divided into subproblems.


• They are also a natural part of mathematical sequences and series, helping us define sequences like Fibonacci numbers alongside triangular numbers.

By using recursion, we naturally break down problems into similar subproblems, aiding not just in defining sequences, but also in understanding mathematical series and processes step by step. This power of recursion makes it a critical concept in both math and computer science.