StudySmarter - The all-in-one study app.

4.8 • +11k Ratings

More than 3 Million Downloads

Free

Proof by Induction

- Calculus
- Absolute Maxima and Minima
- Absolute and Conditional Convergence
- Accumulation Function
- Accumulation Problems
- Algebraic Functions
- Alternating Series
- Antiderivatives
- Application of Derivatives
- Approximating Areas
- Arc Length of a Curve
- Arithmetic Series
- Average Value of a Function
- Calculus of Parametric Curves
- Candidate Test
- Combining Differentiation Rules
- Combining Functions
- Continuity
- Continuity Over an Interval
- Convergence Tests
- Cost and Revenue
- Density and Center of Mass
- Derivative Functions
- Derivative of Exponential Function
- Derivative of Inverse Function
- Derivative of Logarithmic Functions
- Derivative of Trigonometric Functions
- Derivatives
- Derivatives and Continuity
- Derivatives and the Shape of a Graph
- Derivatives of Inverse Trigonometric Functions
- Derivatives of Polar Functions
- Derivatives of Sec, Csc and Cot
- Derivatives of Sin, Cos and Tan
- Determining Volumes by Slicing
- Direction Fields
- Disk Method
- Divergence Test
- Eliminating the Parameter
- Euler's Method
- Evaluating a Definite Integral
- Evaluation Theorem
- Exponential Functions
- Finding Limits
- Finding Limits of Specific Functions
- First Derivative Test
- Function Transformations
- General Solution of Differential Equation
- Geometric Series
- Growth Rate of Functions
- Higher-Order Derivatives
- Hydrostatic Pressure
- Hyperbolic Functions
- Implicit Differentiation Tangent Line
- Implicit Relations
- Improper Integrals
- Indefinite Integral
- Indeterminate Forms
- Initial Value Problem Differential Equations
- Integral Test
- Integrals of Exponential Functions
- Integrals of Motion
- Integrating Even and Odd Functions
- Integration Formula
- Integration Tables
- Integration Using Long Division
- Integration of Logarithmic Functions
- Integration using Inverse Trigonometric Functions
- Intermediate Value Theorem
- Inverse Trigonometric Functions
- Jump Discontinuity
- Lagrange Error Bound
- Limit Laws
- Limit of Vector Valued Function
- Limit of a Sequence
- Limits
- Limits at Infinity
- Limits of a Function
- Linear Approximations and Differentials
- Linear Differential Equation
- Linear Functions
- Logarithmic Differentiation
- Logarithmic Functions
- Logistic Differential Equation
- Maclaurin Series
- Manipulating Functions
- Maxima and Minima
- Maxima and Minima Problems
- Mean Value Theorem for Integrals
- Models for Population Growth
- Motion Along a Line
- Motion in Space
- Natural Logarithmic Function
- Net Change Theorem
- Newton's Method
- Nonhomogeneous Differential Equation
- One-Sided Limits
- Optimization Problems
- P Series
- Particle Model Motion
- Particular Solutions to Differential Equations
- Polar Coordinates
- Polar Coordinates Functions
- Polar Curves
- Population Change
- Power Series
- Ratio Test
- Removable Discontinuity
- Riemann Sum
- Rolle's Theorem
- Root Test
- Second Derivative Test
- Separable Equations
- Simpson's Rule
- Solid of Revolution
- Solutions to Differential Equations
- Surface Area of Revolution
- Symmetry of Functions
- Tangent Lines
- Taylor Polynomials
- Taylor Series
- Techniques of Integration
- The Fundamental Theorem of Calculus
- The Mean Value Theorem
- The Power Rule
- The Squeeze Theorem
- The Trapezoidal Rule
- Theorems of Continuity
- Trigonometric Substitution
- Vector Valued Function
- Vectors in Calculus
- Vectors in Space
- Washer Method
- Decision Maths
- Geometry
- 2 Dimensional Figures
- 3 Dimensional Vectors
- 3-Dimensional Figures
- Altitude
- Angles in Circles
- Arc Measures
- Area and Volume
- Area of Circles
- Area of Circular Sector
- Area of Parallelograms
- Area of Plane Figures
- Area of Rectangles
- Area of Regular Polygons
- Area of Rhombus
- Area of Trapezoid
- Area of a Kite
- Composition
- Congruence Transformations
- Congruent Triangles
- Convexity in Polygons
- Coordinate Systems
- Dilations
- Distance and Midpoints
- Equation of Circles
- Equilateral Triangles
- Figures
- Fundamentals of Geometry
- Geometric Inequalities
- Geometric Mean
- Geometric Probability
- Glide Reflections
- HL ASA and AAS
- Identity Map
- Inscribed Angles
- Isometry
- Isosceles Triangles
- Law of Cosines
- Law of Sines
- Linear Measure and Precision
- Median
- Parallel Lines Theorem
- Parallelograms
- Perpendicular Bisector
- Plane Geometry
- Polygons
- Projections
- Properties of Chords
- Proportionality Theorems
- Pythagoras Theorem
- Rectangle
- Reflection in Geometry
- Regular Polygon
- Rhombuses
- Right Triangles
- Rotations
- SSS and SAS
- Segment Length
- Similarity
- Similarity Transformations
- Special quadrilaterals
- Squares
- Surface Area of Cone
- Surface Area of Cylinder
- Surface Area of Prism
- Surface Area of Sphere
- Surface Area of a Solid
- Surface of Pyramids
- Symmetry
- Translations
- Trapezoids
- Triangle Inequalities
- Triangles
- Using Similar Polygons
- Vector Addition
- Vector Product
- Volume of Cone
- Volume of Cylinder
- Volume of Pyramid
- Volume of Solid
- Volume of Sphere
- Volume of prisms
- Mechanics Maths
- Acceleration and Time
- Acceleration and Velocity
- Angular Speed
- Assumptions
- Calculus Kinematics
- Coefficient of Friction
- Connected Particles
- Constant Acceleration
- Constant Acceleration Equations
- Converting Units
- Force as a Vector
- Kinematics
- Newton's First Law
- Newton's Law of Gravitation
- Newton's Second Law
- Newton's Third Law
- Projectiles
- Pulleys
- Resolving Forces
- Statics and Dynamics
- Tension in Strings
- Variable Acceleration
- Probability and Statistics
- Bar Graphs
- Basic Probability
- Charts and Diagrams
- Conditional Probabilities
- Continuous and Discrete Data
- Frequency, Frequency Tables and Levels of Measurement
- Independent Events Probability
- Line Graphs
- Mean Median and Mode
- Mutually Exclusive Probabilities
- Probability Rules
- Probability of Combined Events
- Quartiles and Interquartile Range
- Systematic Listing
- Pure Maths
- ASA Theorem
- Absolute Value Equations and Inequalities
- Addition and Subtraction of Rational Expressions
- Addition, Subtraction, Multiplication and Division
- Algebra
- Algebraic Fractions
- Algebraic Notation
- Algebraic Representation
- Analyzing Graphs of Polynomials
- Angle Measure
- Angles
- Angles in Polygons
- Approximation and Estimation
- Area and Circumference of a Circle
- Area and Perimeter of Quadrilaterals
- Area of Triangles
- Arithmetic Sequences
- Average Rate of Change
- Bijective Functions
- Binomial Expansion
- Binomial Theorem
- Chain Rule
- Circle Theorems
- Circles
- Circles Maths
- Combination of Functions
- Combinatorics
- Common Factors
- Common Multiples
- Completing the Square
- Completing the Squares
- Complex Numbers
- Composite Functions
- Composition of Functions
- Compound Interest
- Compound Units
- Conic Sections
- Construction and Loci
- Converting Metrics
- Convexity and Concavity
- Coordinate Geometry
- Coordinates in Four Quadrants
- Cubic Function Graph
- Cubic Polynomial Graphs
- Data transformations
- Deductive Reasoning
- Definite Integrals
- Deriving Equations
- Determinant of Inverse Matrix
- Determinants
- Differential Equations
- Differentiation
- Differentiation Rules
- Differentiation from First Principles
- Differentiation of Hyperbolic Functions
- Direct and Inverse proportions
- Disjoint and Overlapping Events
- Disproof by Counterexample
- Distance from a Point to a Line
- Divisibility Tests
- Double Angle and Half Angle Formulas
- Drawing Conclusions from Examples
- Ellipse
- Equation of Line in 3D
- Equation of a Perpendicular Bisector
- Equation of a circle
- Equations
- Equations and Identities
- Equations and Inequalities
- Estimation in Real Life
- Euclidean Algorithm
- Evaluating and Graphing Polynomials
- Even Functions
- Exponential Form of Complex Numbers
- Exponential Rules
- Exponentials and Logarithms
- Expression Math
- Expressions and Formulas
- Faces Edges and Vertices
- Factorials
- Factoring Polynomials
- Factoring Quadratic Equations
- Factorising expressions
- Factors
- Finding Maxima and Minima Using Derivatives
- Finding Rational Zeros
- Finding the Area
- Forms of Quadratic Functions
- Fractional Powers
- Fractional Ratio
- Fractions
- Fractions and Decimals
- Fractions and Factors
- Fractions in Expressions and Equations
- Fractions, Decimals and Percentages
- Function Basics
- Functional Analysis
- Functions
- Fundamental Counting Principle
- Fundamental Theorem of Algebra
- Generating Terms of a Sequence
- Geometric Sequence
- Gradient and Intercept
- Graphical Representation
- Graphing Rational Functions
- Graphing Trigonometric Functions
- Graphs
- Graphs and Differentiation
- Graphs of Common Functions
- Graphs of Exponents and Logarithms
- Graphs of Trigonometric Functions
- Greatest Common Divisor
- Growth and Decay
- Growth of Functions
- Highest Common Factor
- Hyperbolas
- Imaginary Unit and Polar Bijection
- Implicit differentiation
- Inductive Reasoning
- Inequalities Maths
- Infinite geometric series
- Injective functions
- Instantaneous Rate of Change
- Integers
- Integrating Polynomials
- Integrating Trig Functions
- Integrating e^x and 1/x
- Integration
- Integration Using Partial Fractions
- Integration by Parts
- Integration by Substitution
- Integration of Hyperbolic Functions
- Interest
- Inverse Hyperbolic Functions
- Inverse Matrices
- Inverse and Joint Variation
- Inverse functions
- Iterative Methods
- Law of Cosines in Algebra
- Law of Sines in Algebra
- Laws of Logs
- Limits of Accuracy
- Linear Expressions
- Linear Systems
- Linear Transformations of Matrices
- Location of Roots
- Logarithm Base
- Logic
- Lower and Upper Bounds
- Lowest Common Denominator
- Lowest Common Multiple
- Math formula
- Matrices
- Matrix Addition and Subtraction
- Matrix Determinant
- Matrix Multiplication
- Metric and Imperial Units
- Misleading Graphs
- Mixed Expressions
- Modulus Functions
- Modulus and Phase
- Multiples of Pi
- Multiplication and Division of Fractions
- Multiplicative Relationship
- Multiplying and Dividing Rational Expressions
- Natural Logarithm
- Natural Numbers
- Notation
- Number
- Number Line
- Number Systems
- Numerical Methods
- Odd functions
- Open Sentences and Identities
- Operation with Complex Numbers
- Operations with Decimals
- Operations with Matrices
- Operations with Polynomials
- Order of Operations
- Parabola
- Parallel Lines
- Parametric Differentiation
- Parametric Equations
- Parametric Integration
- Partial Fractions
- Pascal's Triangle
- Percentage
- Percentage Increase and Decrease
- Percentage as fraction or decimals
- Perimeter of a Triangle
- Permutations and Combinations
- Perpendicular Lines
- Points Lines and Planes
- Polynomial Graphs
- Polynomials
- Powers Roots And Radicals
- Powers and Exponents
- Powers and Roots
- Prime Factorization
- Prime Numbers
- Problem-solving Models and Strategies
- Product Rule
- Proof
- Proof and Mathematical Induction
- Proof by Contradiction
- Proof by Deduction
- Proof by Exhaustion
- Proof by Induction
- Properties of Exponents
- Proportion
- Proving an Identity
- Pythagorean Identities
- Quadratic Equations
- Quadratic Function Graphs
- Quadratic Graphs
- Quadratic functions
- Quadrilaterals
- Quotient Rule
- Radians
- Radical Functions
- Rates of Change
- Ratio
- Ratio Fractions
- Rational Exponents
- Rational Expressions
- Rational Functions
- Rational Numbers and Fractions
- Ratios as Fractions
- Real Numbers
- Reciprocal Graphs
- Recurrence Relation
- Recursion and Special Sequences
- Remainder and Factor Theorems
- Representation of Complex Numbers
- Rewriting Formulas and Equations
- Roots of Complex Numbers
- Roots of Polynomials
- Roots of Unity
- Rounding
- SAS Theorem
- SSS Theorem
- Scalar Triple Product
- Scale Drawings and Maps
- Scale Factors
- Scientific Notation
- Second Order Recurrence Relation
- Sector of a Circle
- Segment of a Circle
- Sequences
- Sequences and Series
- Series Maths
- Sets Math
- Similar Triangles
- Similar and Congruent Shapes
- Simple Interest
- Simplifying Fractions
- Simplifying Radicals
- Simultaneous Equations
- Sine and Cosine Rules
- Small Angle Approximation
- Solving Linear Equations
- Solving Linear Systems
- Solving Quadratic Equations
- Solving Radical Inequalities
- Solving Rational Equations
- Solving Simultaneous Equations Using Matrices
- Solving Systems of Inequalities
- Solving Trigonometric Equations
- Solving and Graphing Quadratic Equations
- Solving and Graphing Quadratic Inequalities
- Special Products
- Standard Form
- Standard Integrals
- Standard Unit
- Straight Line Graphs
- Substraction and addition of fractions
- Sum and Difference of Angles Formulas
- Sum of Natural Numbers
- Surds
- Surjective functions
- Tables and Graphs
- Tangent of a Circle
- The Quadratic Formula and the Discriminant
- Transformations
- Transformations of Graphs
- Translations of Trigonometric Functions
- Triangle Rules
- Triangle trigonometry
- Trigonometric Functions
- Trigonometric Functions of General Angles
- Trigonometric Identities
- Trigonometric Ratios
- Trigonometry
- Turning Points
- Types of Functions
- Types of Numbers
- Types of Triangles
- Unit Circle
- Units
- Variables in Algebra
- Vectors
- Verifying Trigonometric Identities
- Writing Equations
- Writing Linear Equations
- Statistics
- Bias in Experiments
- Binomial Distribution
- Binomial Hypothesis Test
- Bivariate Data
- Box Plots
- Categorical Data
- Categorical Variables
- Central Limit Theorem
- Chi Square Test for Goodness of Fit
- Chi Square Test for Homogeneity
- Chi Square Test for Independence
- Chi-Square Distribution
- Combining Random Variables
- Comparing Data
- Comparing Two Means Hypothesis Testing
- Conditional Probability
- Conducting a Study
- Conducting a Survey
- Conducting an Experiment
- Confidence Interval for Population Mean
- Confidence Interval for Population Proportion
- Confidence Interval for Slope of Regression Line
- Confidence Interval for the Difference of Two Means
- Confidence Intervals
- Correlation Math
- Cumulative Frequency
- Data Analysis
- Data Interpretation
- Discrete Random Variable
- Distributions
- Dot Plot
- Empirical Rule
- Errors in Hypothesis Testing
- Estimator Bias
- Events (Probability)
- Frequency Polygons
- Generalization and Conclusions
- Geometric Distribution
- Histograms
- Hypothesis Test for Correlation
- Hypothesis Test of Two Population Proportions
- Hypothesis Testing
- Inference for Distributions of Categorical Data
- Inferences in Statistics
- Large Data Set
- Least Squares Linear Regression
- Linear Interpolation
- Linear Regression
- Measures of Central Tendency
- Methods of Data Collection
- Normal Distribution
- Normal Distribution Hypothesis Test
- Normal Distribution Percentile
- Point Estimation
- Probability
- Probability Calculations
- Probability Distribution
- Probability Generating Function
- Quantitative Variables
- Quartiles
- Random Variables
- Randomized Block Design
- Residual Sum of Squares
- Residuals
- Sample Mean
- Sample Proportion
- Sampling
- Sampling Distribution
- Scatter Graphs
- Single Variable Data
- Skewness
- Standard Deviation
- Standard Normal Distribution
- Statistical Graphs
- Statistical Measures
- Stem and Leaf Graph
- Sum of Independent Random Variables
- Survey Bias
- Transforming Random Variables
- Tree Diagram
- Two Categorical Variables
- Two Quantitative Variables
- Type I Error
- Type II Error
- Types of Data in Statistics
- Venn Diagrams

If a domino falls in a chain, the next domino will surely fall too. Since this second domino is falling, the next one in the chain will certainly fall as well. Since this third domino is falling, the fourth will fall too, and then the fifth, and then the sixth, and so on. Therefore, if it is known that a domino falling will knock over the next domino in the chain, you can say for a fact that knocking over the first domino in the chain will cause all the dominoes to fall. This resembles a type of mathematical proof called **proof by induction**.

Proof by induction is a way of proving that something is true for every positive integer.

**Proof by induction** is a way of proving that a certain statement is true for every positive integer \(n\). Proof by induction has four steps:

- Prove the
**base case**: this means proving that the statement is true for the**initial value**, normally \(n = 1\) or \(n=0.\) - Assume that the statement is true for the value \( n = k.\) This is called the
**inductive hypothesis.** - Prove the
**inductive step**: prove that if the assumption that the statement is true for \(n=k\), it will also be true for \(n=k+1\). - Write a
**conclusion**to explain the proof, saying: "If the statement is true for \(n=k\), the statement is also true for \(n=k+1\). Since the statement is true for \(n=1\), it must also be true for \(n=2\), \(n=3\), and for any other positive integer."

Proof by induction is an incredibly useful tool to prove a wide variety of things, including problems about divisibility, matrices and series.

First, let's look at an example of a divisibility proof using induction.

Prove that for all positive integers \(n\), \(3^{2n+2} + 8n -9 \) is divisible by 8.

**Solution**

First define \(f(n) = 3^{2n+2} + 8n -9 \).

Step 1: Now consider the base case. Since the question says for all positive integers, the base case must be \(f(1)\). You can substitute \(n=1\) into the formula to get

\[ \begin{align} f(1) = 3^{2+2} + 8 - 9 & = 3^4 - 1 \\ & = 81 - 1 \\ & = 80. \end{align} \]

80 is clearly divisible by 10, hence the condition is true for the base case.

Step 2: Next, state the inductive hypothesis. This assumption is that \(f(k) = 3^{2k + 2} + 8k - 9 \) is divisible by 8.

Step 3: Now, consider \(f(k+1)\). The formula will be:

\[ \begin{align} f(k+1) & = 3^{2(k+1)+2} + 8(k + 1) - 9 \\ & = 3^{2k + 4} + 8k + 8 -9 \\ & = 3^{2k+4} + 8k -9 + 8. \end{align} \]

It may seem weird to write it like this, without simplifying the \(8-9\) to become \(-1\). There is a good reason to do this: you want to keep the formula as similar to the formula of \(f(k)\) as you can since you need to transform it into this somehow.

To do this transformation, notice that the first term in \(f(k+1) \) is the same as the first term in \(f(k)\) but multiplied by \(3^2 = 9\). Hence, you can split this up into two separate parts.

\[ \begin{align} f(k+1) & = 9 \cdot 3^{2k+2} + 8k -9 + 8 \\ & = 3^{2k+2} + 8 \cdot 3^{2k+2} + 8k -9 + 8 \\ & = (3^{2k+2} + 8k -9) + 8 \cdot 3^{2k+2} + 8 \\ & = f(k) + 8 \cdot 3^{2k+2} + 8. \end{align} \]

The first term in this is divisible by 8 because of the assumption, and the second and third terms are multiples of 8, thus they are divisible by 8 too. Since this is the sum of different terms that are all divisible by 8, \(f(k+1)\) must also be divisible by 8 too, assuming the inductive hypothesis is true. Hence, you have proven the inductive step.

Step 4: Finally, remember to write the conclusion. This should sound something like:

If it is true that \( f(k) \) is divisible by 8, then it will also be true that \(f(k+1) \) is divisible by 8. Since it is true that \(f(1)\) is divisible by 8, it is true that \(f(n)\) is divisible by 8 for all positive integers \(n\).

In the next sections, you will look at using proof by induction to prove some key results in Mathematics.

Here is a proof by induction where you must use trigonometric identities to prove an inequality.

Prove that for any non-negative integer \(n\),

\[ |\sin{(nx)}| \leq n \sin{x}, \]

for \( x \in (0, \pi) \).

**Solution**

Step 1: The base case is clear, since substituting in \(n=1\) makes the inequality \( |\sin{x}| \leq{\sin{x}}\), which is true for \( x \in (0, \pi) \).

Step 2: For the induction hypothesis, assume that \[ | \sin{(mx)} | \leq m \sin{x}. \]

Step 3: You must now prove that \( |\sin{((m+1)x)}| \leq (m+1) \sin{x}. \) First, you can expand the bracket of the left hand side:

\[ |\sin{((m+1)x)}| = |\sin{(mx + x)}| \]

Now, you can use the trigonometric sum of angles formula for the sine function.

\[ |\sin{((m+1)x)}| = |\sin{(mx)} \cos{(m)} + \cos{(mx)} \sin{(m)}|. \]

From here, you can use the **triangle inequality for absolute values:** \( | a + b| \leq |a| + |b| \).

\[ |\sin{((m+1)x)}| \leq |\sin{(mx)} \cos{(x)}| + |\cos{(mx)} \sin{(x)}|. \]

Remember that \( \cos{(mx)} \) and \( \cos{(x)} \) are less than one. Hence, you can create a new upper bound by estimating the cosine functions as 1:

\[ \begin{align} |\sin{((m+1)x)}| &\leq |\sin{(mx)} \cos{(x)}| + |\cos{(mx)} \sin{(x)}| \\ &\leq |\sin{(mx)}| + |\sin{(x)}|. \end{align} \]

From here, notice that there is \( |\sin{(mx)}| \) on the left-hand side. This is where you can use the inductive hypothesis. You know \( |\sin{(mx)}| \leq m \sin{x}\), so you can create another upper bound:

\[ \begin{align} |\sin{((m+1)x)}| &\leq |\sin{(mx)}| + |\sin{(x)}| \\ &\leq m \sin{(x)} + |\sin{(x)}|. \end{align} \]

Finally, as was stated in the base case, \( |\sin{(x)}| \leq \sin{(x)} \). S,

\[ |\sin{((m+1)x)}| \leq m \sin{(x)} + \sin{(x)} = (m+1)\sin{(x)}, \]

as required.

Step 4: Finally, state the conclusion. We have proved that the inequality holds for \( n = m+1 \) if it holds for \( n = m.\) Since it holds for \(n=1\), by induction it will hold for all positive integers.

The Fundamental Theorem of Arithmetic states that every integer \(n \geq 2\) can be written uniquely as a product of primes. This proof splits into two parts:

Proof that any integer \(n \geq 2\) can be written as a product of primes, and

Proof that this product of primes is unique (up to the order in which the primes are written).

The first part can be proved using a specific type of induction called **strong induction.**

**Strong Induction**** **is the same as regular induction, but rather than assuming that the statement is true for \(n=k\), you assume that the statement is true for any \(n \leq k\). The steps for strong induction are:

- The
**base case**: prove that the statement is true for the initial value, normally \(n = 1\) or \(n=0.\) - The
**inductive hypothesis:**assume that the statement is true for all \( n \le k.\) - The
**inductive step**: prove that if the assumption that the statement is true for \(n \le k\), it will also be true for \(n=k+1\). - The
**conclusion:**write: "If the statement is true for all \(n \le k\), the statement is also true for \(n=k+1\). Since the statement is true for \(n=1\), it must also be true for \(n=2\), \(n=3\), and for any other positive integer."

Let's use strong induction to prove the first part of the Fundamental Theorem of Arithmetic.

Prove that any integer \(n \geq 2\) can be written as a product of primes.

**Solution**

Step 1: First, prove the base case, which in this case requires \(n=2\). Since \(2 \) is already a prime number, it is already written as a product of primes, and hence the base case it true.

Step 2: Next, state the inductive hypothesis. You will assume that for any \( 2 \leq n \leq k\), \(n\) can be written as a product of primes.

Step 3: Finally, you must use the assumption to prove that \(n=k+1 \) can be written as a product of primes. There are two cases:

- \(k+1\) is a prime number, in which case it is clearly already written as the product of primes.
- \(k+1\) is not a prime number and there must be a composite number.

If \(k+1\) is not a prime number, this means it must be divisible by a number other than itself or 1. This means there exists \(a_1\) and \(a_2\), with \(2 \le a_1\) and \(a_2 \le k\), such that \(k+1 = a_1 a_2. \) By the inductive hypothesis, \(a_1\) and \(a_2\) must have a prime decomposition, since \(2 \le a_1\) and \(a_2 \le k\). This means there exist prime numbers \( p_1,\dots ,p_i\) and \(q_1,\dots ,q_j\) such that

\[ \begin{align} a_1 & = p_1\dots p_i \\ a_2 & = q_1 \dots q_j. \end{align} \]

Finally, since \(k+1 = a_1 a_2, \) you have:

\[ k+1 = p_1\dots p_i q_1\dots q_j \]

which is a product of primes. Hence, this is a prime decomposition for \(k+1\).

Step 4: \(k+1\) will have a prime decomposition if all numbers \(n\), \(2 \leq n \leq k \) also have a prime decomposition. Since 2 has a prime decomposition, therefore by induction every positive integer greater than or equal to 2 must have a prime decomposition.

The proof that this product of primes is unique is a bit different, but nothing too complex. It uses **proof by contradiction**.

Prove that the prime factorisation for any number \(n \geq 2\) is unique.

**Solution**

Suppose you have two different prime factorisations for \(n\). These will be

\[ \begin{align} n & = p_1\dots p_i \mbox{ and }\\ n & = q_1\dots q_j. \end{align} \]

You can set these as equal since they both equal \(n\):

\[ p_1\dots p_i = q_1\dots q_j \]

Since the left-hand side has the factor \( p_1 \) in it, both sides must be divisible by \(p_1\). Since \(p_1\) is prime and all the \(q\)'s are also prime, it must be that one of the \(q\)'s is equal to \(p_1\). Call this \(q_k\). Now, you can cancel out \(p_1\) and \(q_k\) to get:

\[ p_2\dots p_i = q_1\dots q_{k-1} q_{k+1}\dots q_j. \]

You can do this same process with the \(p_2\), and then the \(p_3\), until you run out of either \(p\)'s or \(q\)'s. If you run out of \(p\)'s first, the left-hand side will now be 1. This means the right-hand side must be equal to 1 as well, but since it is made only of primes, it must mean that all of the primes have been cancelled out. Thus, for every \(p\) in the list, there must be a \(q\) that it is equal to. Hence, the two factorisations were in fact the same.

The process is the same if you assume that you run out of \(q\)'s first.

The sum of the squares of the first \(n\) numbers is given by the formula:

\[ 1^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}. \]

Let's prove this by induction.

Prove that for any positive integer \(n\),

\[ 1^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}. \]

**Solution**

Step 1: First, consider the base case, when \(n=1\). The left-hand side is clearly just 1, while the right-hand side becomes

\[ \frac{1 \cdot 2 \cdot 3}{6} = \frac{6}{6} = 1. \]

Hence, the base case is correct.

Step 2: Next, write the induction hypothesis. This is that

\[ 1^2 + \dots + m^2 = \frac{m(m+1)(2m+1)}{6}. \]

Step 3: Finally, prove the inductive step. The left-hand side, for \(n=m+1\), will be:

\[ 1^2 +\dots + m^2 + (m+1)^2 = (1^2 +\dots + m^2) + (m+1)^2. \]

The first \(n\) terms in this are in the inductive hypothesis. Thus, you can replace these with the right-hand side from the inductive hypothesis:

\[ \begin{align} 1^2 +\dots + m^2 + (m+1)^2 & = \frac{m(m+1)(2m+1)}{6} + (m+1)^2 \\ & = \frac{m(m+1)(2m+1) + 6(m+1)^2}{6} \\ & = \frac{(m+1)\left[m(2m+1) + 6(m+1)\right]}{6}. \end{align}\]

Next, expand the bit inside of the square brackets, so you will have a quadratic. Then you can solve the quadratic normally:

\[ \begin{align} 1^2 +\dots + m^2 + (m+1)^2 & = \frac{(m+1)\left[2m^2+1m + 6m+6\right]}{6} \\ & = \frac{(m+1)[2m^2 + 7m + 6}{6} \\ & = \frac{(m+1)(m+2)(2m+3)}{6} \\ & = \frac{(m+1)((m+1)+1)(2(m+1)+1)}{6}, \end{align}\]

as required. Thus, you have proven the inductive step.

Step 4: Finally, write the conclusion. If the sum of squares formula is true for any positive integer \(m\), then it will be true for \(m+1\). Since it is true for \(n=1\), it is true for all positive integers.

**Binet's Formula **is a way of writing the Fibonacci numbers in a closed form expression.

**Binet's Formula:**

\[F_n = \frac{\phi^n - \hat{\phi}^n}{\sqrt{5}}, \]

where \(F_n\) is the \(n\)th Fibonacci number, meaning \(F_n\) satisfies the recurrence initial value problem:

\[ \begin{align} &F_n = F_{n-1} + F_{n-2}, \\ &F(0) =0, \\ &F(1)=1. \end{align} \]

The number \(\phi\) is known as the **golden mean**, and is the value:

\[\phi = \frac{1+\sqrt{5}}{2}\]

and \(\hat{\phi} = 1 - \phi.\)

Notice that \( \phi\) and \( \hat{\phi} \) are the solutions to the quadratic equation \( x^2 = 1 + x.\) This result is very important the the proof below.

Prove Binet's Formula using induction.

**Solution**

Step 1: First, prove the induction base. This will be for \(F_0\) and \(F_1\). For \(F_0\):

\[\frac{\phi^0 - \hat{\phi}^0}{\sqrt{5}} = \frac{1-1}{5} = 0, \]

which is the value of \( F_0\) as expected.

For \(F_1\):

\[ \begin{align} \frac{\phi - \hat{\phi}}{\sqrt{5}} & = \frac{\frac{1+\sqrt{5}}{2} \frac{1-\sqrt{5}}{2}}{\sqrt{5}} \\ & = \frac{1}{\sqrt{5}}\cdot \frac{1-1 +\sqrt{5} + \sqrt{5}}{2} \\ & = 1, \end{align} \]

which is the expected answer. Thus, the induction base is proven.

Step 2: Next, state the induction hypothesis. In this case, strong induction must be used. The hypothesis is that for any \( 0 \leq i \leq k+1, \)

\[ F_i = \frac{\phi^i + \hat{\phi}^i}{\sqrt{5}}. \]

Step 3: Now you must prove the induction step, which is that

\[F_{k+2} = \frac{\phi^{k+2} + \hat{\phi}^{k+2}}{\sqrt{5}}.\]

Start with the right-hand side and try and simplify it until you reach the left-hand side. First, start by splitting the power of \(k+2\) into 2 separate terms, one with the power of \(k\) and the other with the power of \(2\).

\[ \frac{\phi^{k+2} + \hat{\phi}^{k+2}}{\sqrt{5}} = \frac{\phi^2 \phi^k + \hat{\phi}^2 \hat{\phi}^k}{\sqrt{5}} \]

Now, you can use the result that \( \phi^2 = 1 + \phi\) and \( \hat{\phi}^2 = 1 + \hat{\phi} \).

\[ \begin{align} \frac{\phi^{k+2} + \hat{\phi}^{k+2}}{\sqrt{5}} & = \frac{(1+\phi) \phi^{k} + (1+\hat{\phi}) \hat{\phi}^{k}}{\sqrt{5}} \\ & = \frac{\phi^{k} + \hat{\phi}^{k} + \phi^{k+1} + \hat{\phi}^{k+1}}{\sqrt{5}} \\ & = \frac{\phi^{k} + \hat{\phi}^{k}}{\sqrt{5}} + \frac{\phi^{k+1} + \hat{\phi}^{k+1}}{\sqrt{5}} \\ & = F_k + F_{k+1} \\ & = F_{k+2}. \end{align} \]

And thus, the induction step has been proved. The step that gets the answer to \( F_k + F_{k+1} \) requires the use of the induction hypothesis to get there.

Step 4: Finally, the conclusion: If Binet's Formula holds for all non-negative integers up to \(k+1\), then the formula will hold for \(k+2\). Since the formula holds for \(F_0\) and \(F_1\), the formula will hold for all non-negative integers.

- Proof by induction is a way of proving that something is true for every positive integer. It works by showing that if the result holds for \(n=k\), the result must also hold for \(n=k+1\).
- Proof by induction starts with a
**base case,**where you must show that the result is true for it's initial value. This is normally \( n = 0\) or \( n = 1\). - You must next make an
**inductive hypothesis,**which is assuming that the result holds for \(n=k\). In**strong induction**, the inductive hypothesis is that the result holds for all \( n \leq k.\) - You must next prove the
**inductive step**, showing that if the inductive hypothesis holds, the result will also hold for \( n = k+1\). - Finally, you must write a
**conclusion**, explaining why the proof works.

- Fig 1: Fibonacci Spiral over tiled squares (https://commons.wikimedia.org/wiki/File:Fibonacci_Spiral.svg) by Romain, licensed by CC BY-SA 4.0 (https://creativecommons.org/licenses/by-sa/4.0/?ref=openverse#).

Proof by induction works because you are proving that if the result holds for n=k, it must also hold for n=k+1. Hence, if you show it is true for n=1, it must be true for:

- 1+1 = 2,
- 2+1 = 3,
- 3+1 = 4 etc.

More about Proof by Induction

Be perfectly prepared on time with an individual plan.

Test your knowledge with gamified quizzes.

Create and find flashcards in record time.

Create beautiful notes faster than ever before.

Have all your study materials in one place.

Upload unlimited documents and save them online.

Identify your study strength and weaknesses.

Set individual study goals and earn points reaching them.

Stop procrastinating with our study reminders.

Earn points, unlock badges and level up while studying.

Create flashcards in notes completely automatically.

Create the most beautiful study materials using our templates.

Sign up to highlight and take notes. It’s 100% free.