Prove 1+2+...+n=n(n+1)/2 by induction for n≥1.
Answer and explanation
The base n=1 holds. Assuming the formula for n, add n+1 to get n(n+1)/2+(n+1)=(n+1)(n+2)/2.
Credit both the base and valid induction step.
Subjects
Discrete mathematics
Choose questions individually, practise online, or create a worksheet with matching answers. Counts include generated variants, not only authored originals.
Make a worksheet8 question instances
Sample exercises
A finite undirected graph has degree sum 30. How many edges does it have?
Answer and explanation
15
Each edge contributes two to the degree sum.
A tree has 12 vertices. How many edges does it have?
Answer and explanation
11
A finite tree has n−1 edges.
What must be true of the number of odd-degree vertices in a finite undirected graph?
- It equals the total number of edges
- It is even
- It is always zero
- It is always odd
Answer and explanation
It is even
The degree sum is even, so the sum of odd contributions contains an even number of odd terms.
Why is assuming the statement for n+1 while proving it for n+1 circular?
Answer and explanation
The desired conclusion is used as a premise. The induction hypothesis must concern a previously established case, typically n.
Credit identifying the unjustified assumption.
How many subsets does a 5-element set have?
Answer and explanation
32
Each element is independently included or excluded, giving 2^5.
Study notes
Induction, graphs and discrete reasoning
Prove a base case and a step from n to n+1; neither alone suffices.
UniversityInduction, graphs and discrete reasoning · revision notes
Prove a base case and a step from n to n+1; neither alone suffices.
UniversityRelated courses
Mathematics4 lessons
University calculus and multivariable methods
Practise improper integrals, series, gradients and multiple integrals, with explicit conditions and worked examples.
32 quiz questions · University
Mathematics3 lessons
Linear algebra: spaces, eigenvectors and fitting
Develop matrix, vector-space and projection reasoning before using least squares.
24 quiz questions · University
Mathematics3 lessons
Differential equations and numerical methods
Connect initial conditions, linear differential equations and numerical approximation with error and conditioning.
24 quiz questions · University
Mathematics2 lessons
Probability models and continuous distributions
Work with conditional probability, normalization, densities and expectation.
16 quiz questions · University
Mathematics3 lessons
Real analysis: limits and rigorous reasoning
Build epsilon proofs and distinguish pointwise convergence, uniform convergence and compactness.
24 quiz questions · Advanced university
Mathematics3 lessons
Abstract algebra and discrete proofs
Study groups, vector-space quotients and proof techniques with carefully scoped definitions.
24 quiz questions · Advanced university, University
Mathematics5 lessons
Advanced mathematical methods
Study complex analysis, residues, Fourier series, PDE boundary conditions and convexity through focused lessons.
40 quiz questions · Advanced university
Mathematics4 lessons
Practical statistics and inference
Learn descriptive statistics, probability, sampling and inference with worked reasoning.
32 quiz questions · University