For questions about mathematical induction, a method of mathematical proof. Mathematical induction generally proceeds by proving a statement for some integer, called the *base case*, and then proving that if it holds for one integer then it holds for the next integer. This tag is primarily meant ...

learn more… | top users | synonyms

30
votes
7answers
6k views

Proving $1^3+ 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$ using induction

How can I prove that $$1^3+ 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$$ for all $n \in \mathbb{N}$? I am looking for a proof using mathematical induction. Thanks
25
votes
9answers
5k views

Why $a^n - b^n$ is divisible by $a-b$?

I did some mathematical induction problems on divisibility $9^n$ $-$ $2^n$ is divisible by 7. $4^n$ $-$ $1$ is divisible by 3. $9^n$ $-$ $4^n$ is divisible by 5. Can these be generalized as $a^n$ ...
39
votes
5answers
4k views

Dominoes and induction, or how does induction work?

I've never really understood why math induction is supposed to work. You have these 3 steps: Prove true for base case (n=0 or 1 or whatever) Assume true for n=k. Call this the induction ...
6
votes
5answers
1k views

Alternating sum of binomial coefficients: given $n \in \mathbb N$, prove $\sum^n_{k=0}(-1)^k {n \choose k} = 0$

I tried to solve it using induction, but that got me no were, in the middle of the equation stat appearing ks that I don't see how to get out of the equation. I think the easiest way to prove it, it's ...
7
votes
5answers
562 views

Proof writing: how to write a clear induction proof?

What is an effective way to write induction proofs? Essentially, are there any good examples or templates of induction proofs that may be helpful (for beginners, non-English-native students, etc.)? ...
20
votes
6answers
4k views

Why is mathematical induction a valid proof technique? [duplicate]

Context: I'm studying for my discrete mathematics exam and I keep running into this question that I've failed to solve. The question is as follows. Problem: The main form for normal induction over ...
78
votes
6answers
8k views

Induction on Real Numbers

One of my Fellows asked me whether total induction is applicable to real numbers, too ( or at least all real numbers ≥ 0) . We only used that for natural numbers so far. Of course you have to change ...
8
votes
2answers
5k views

Inductive proof that ${2n\choose n}=\sum{n\choose i}^2.$

I would like to prove inductively that $${2n\choose n}=\sum_{i=0}^n{n\choose i}^2.$$ I know a couple of non-inductive proofs, but I can't do it this way. The inductive step eludes me. I tried naively ...
12
votes
6answers
3k views

Proving $\sum\limits_{k=1}^{n}{\frac{1}{\sqrt{k}}\ge\sqrt{n}}$ with induction

I am just starting out learning mathematical induction and I got this homework question to prove with induction but I am not managing. $$\sum\limits_{k=1}^{n}{\frac{1}{\sqrt{k}}\ge\sqrt{n}}$$ ...
6
votes
1answer
2k views

Show that $n$ lines separate the plane into $\frac{(n^2+n+2)}{2}$ regions

Show that $n$ lines separate the plane into $\frac{(n^2+n+2)}{2}$ regions if no two of these lines are parallel and no three pass through a common point. I know we start with the base case, ...
12
votes
10answers
1k views

Prove by induction that for all $n \geq 3$: $n^{n+1} > (n+1)^n$

I am currently helping a friend of mine with his preperations for his next exam. A big topic of the exam will be induction, thus I told him he should practice this a lot. As at the beginning he had no ...
1
vote
2answers
1k views

Proving $\sum\limits_{i=0}^n i 2^{i-1} = (n+1) 2^n - 1$ by induction

I'm trying to apply an induction proof to show that $((n+1) 2^n - 1 $ is the sum of $(i 2^{i-1})$ from $0$ to $n$. the base case: L.H.S = R.H.S we assume that $(k+1) 2^k - 1 $ is true. we need to ...
3
votes
2answers
469 views

What is the formula for $1/(1\cdot 2)+1/(2\cdot 3)+1/(3\cdot 4)+\ldots +1/(n(n+1))$

How can I find the formula for the following equation? $$\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+\ldots +\frac{1}{n(n+1)}$$ More importantly, how would you approach finding the ...
5
votes
5answers
12k views

Proof that $n^2 < 2^n$

How do I prove the following statement by induction? $$n^2 \lt 2^n$$ $P(n)$ is the statement $n^2 \lt 2^n$ Claim: For all $n \gt k$, where $k$ is any integer, $P(n)$ (since $k$ is any integer, I ...
4
votes
2answers
3k views

Proof the inequality $n! \geq 2^n$ by induction

I'm having difficulity solving an exercise in my course. The question is: Prove that $n!\geq 2^n$. We have to do this with induction. I started like this: The lowest natural number where the ...
9
votes
4answers
2k views

Induction Proof that $x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1})$

This question is from [Number Theory George E. Andrews 1-1 #3]. Prove that $$x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1}).$$ This problem is driving me crazy. $$x^n-y^n = ...
9
votes
3answers
3k views

Proof by induction of Bernoulli's inequality: $(1 + x)^n \geq 1 + nx$

I'm asked to used induction to prove Bernoulli's Inequality: If $1+x>0$, then $(1+x)^n\geq 1+nx$ for all $n\in\mathbb{N}$. This what I have so far: Let $n=1$. Then $1+x\geq 1+x$. This is true. Now ...
9
votes
4answers
3k views

What is the second principle of finite induction?

I understand the principle of finite induction, but my book then mentions that there is a variant of the first where requirement b is changed to If $k$ is a positive integer such that $1,2, ...
6
votes
2answers
2k views

Inductive proof of the closed formula for the Fibonacci sequence [duplicate]

Fibonacci numbers $f(n)$ are defined recursively: $f(n) = f(n-1) +f(n-2)$ for $n > 2$ and $f(1) = 1$, $f(2) = 1$. They also admit a simple closed form: $$\sqrt 5 f( n ) = \left(\dfrac{1+ \sqrt ...
0
votes
2answers
202 views

Proving the geometric sum formula by induction

$$\sum_{k=0}^nq^k = \frac{1-q^{n+1}}{1-q}$$ I want to prove this by induction. Here's what I have. $$\frac{1-q^{n+1}}{1-q} + q^{n+1} = \frac{1-q^{n+1}+q^{n+1}(1-q)}{1-q}$$ I wanted to factor a ...
23
votes
5answers
1k views

How does one actually show from associativity that one can drop parentheses?

I've always heard this reasoning, and it makes obvious sense, but how do you actually show it for some arbitrary product? Would it be something like this? ...
19
votes
6answers
2k views

Induction: $\sum_{k=0}^n \binom nk k^2 = n(1+n)2^{n-2}$

I found crazy (for me at least) induction example, in fact it just would be nice to prove. (Even have problems with starting) Any hints are highly valued: ...
12
votes
5answers
4k views

Show that $11^{n+1}+12^{2n-1}$ is divisible by $133$.

Problem taken from a paper on mathematical induction by Gerardo Con Diaz. Although it doesn't look like anything special, I have spent a considerable amount of time trying to crack this, with no luck. ...
5
votes
6answers
2k views

Prove that $(a-b) \mid (a^n-b^n)$

I'm trying to prove by induction that for all $a,b \in \mathbb{Z}$ and $n \in \mathbb{N}$, that $(a-b) \mid (a^n-b^n)$. The base case was trivial, so I started by assuming that $(a-b) \mid (a^n-b^n)$. ...
5
votes
4answers
3k views

Prove by Mathematical Induction: $1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!) = (n+1)!-1$

Prove by Mathematical Induction . . . $1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!) = (n+1)!-1$ I tried solving it, but I got stuck near the end . . . a. Basis Step: $(1)(1!) = (1+1)!-1$ $1 = ...
5
votes
5answers
5k views

Simple Proof by induction: “9 divides $n^3 + (n+1)^3 + (n+2)^3$”

I'm trying to prove using induction that 9 divides $n^3 + (n+1)^3 + (n+2)^3$ whenever $n$ is a non-negative integer. So far, I have: Base case: P(1) = (1) + (8) + (27) = 36, 36 can be divided by 9 ...
4
votes
3answers
2k views

induction proof: $\sum_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$

I encountered the following induction proof on a practice exam for calculus: $$\sum_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$$ I have to prove this statement with induction. Can anyone please help me ...
2
votes
5answers
5k views

Proof by induction that $ \sum_{i=1}^n 3i-2 = \frac{n(3n-1)}{2} $

I'm starting to understand how induction works (with the whole $k \to k+1$ thing), but I'm not exactly sure how summations play a role. I'm a bit confused by this question specifically: $$ ...
50
votes
10answers
2k views

Fake induction proofs

Question: Can you provide an example of a claim where the base case holds but there is a subtle flaw in the inductive step that leads to a fake proof of a clearly erroneous result? [Note: Please do ...
24
votes
1answer
40k views

What's the difference between simple induction and strong induction?

I just started to learn induction in my first year course. I'm having a difficult time grasping the concept. I believe I understand the basics but could someone summarize simple induction and strong ...
9
votes
3answers
19k views

How to prove a formula for the sum of powers of $2$ by induction?

How do I prove this by induction? Prove that for every natural number n, $ 2^0 + 2^1 + ... + 2^n = 2^{n+1}-1$ Here is my attempt. Base Case: let $ n = 0$ Then, $2^{0+1} - 1 = 1$ Which is true. ...
8
votes
3answers
1k views

Prove by induction Fibonacci equality

[question:] Prove by induction that the i th Fibonacci number satisfies the equality $$F_i=\frac{\phi^i-\hat{\phi^i}}{\sqrt5}$$where $\phi$ is the golden ratio and $\hat{\phi}$ is its conjugate. ...
3
votes
5answers
407 views

Proving the total number of subsets of S is equal to $2^n$

Student here! Just reading Liebecks Introduction to pure mathematics for fun and I made an attempt at proving the total number of subsets of S is equal to $2^n$. I realized that the total number of ...
4
votes
2answers
999 views

Induction proof concerning a sum of binomial coefficients: $\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$ [duplicate]

I'm looking for a proof of this identity but where j=m not j=0 http://www.proofwiki.org/wiki/Sum_of_Binomial_Coefficients_over_Upper_Index $$\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$$
2
votes
5answers
159 views

Proving $ 1+\frac{1}{4}+\frac{1}{9}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$ for all $n\geq 2$ by induction

Question: Let $P(n)$ be the statement that $1+\dfrac{1}{4}+\dfrac{1}{9}+\cdots +\dfrac{1}{n^2} <2- \dfrac{1}{n}$. Prove by mathematical induction. Use $P(2)$ for base case. Attempt at ...
2
votes
6answers
135 views

Prove by induction that $n^2<n!$

How can I show that $n^2<n!$ for all $n\geq 4$ Step 1 For $n=1$, the LHS=$4^2=16$ and RHS=$4!=24$. So LHS$<$ RHS. Step 2 Suppose the result be true for $n=k$ i.e., $k^2<k!$ Step 3 ...
2
votes
3answers
136 views

How to prove this statement: $\binom{r}{r}+\binom{r+1}{r}+\cdots+\binom{n}{r}=\binom{n+1}{r+1}$

Let $n$ and $r$ be positive integers with $n \ge r$. Prove that Still a beginner here. Need to learn formatting. I am guessing by induction? Not sure what or how to go forward with this. Need help ...
2
votes
2answers
537 views

Inductive proof of a formula for Fibonacci numbers

May someone help me? I am trying to use induction to prove that the formula for finding the $n$-th term of the Fibonacci sequence is: ...
37
votes
19answers
9k views

Examples of mathematical induction

What are the best examples of mathematical induction available at the secondary-school level---totally elementary---that do not involve expressions of the form $\bullet+\cdots\cdots\cdots+\bullet$ ...
23
votes
5answers
2k views

What makes induction a valid proof technique?

What makes induction (over natural numbers) a valid proof technique? Is $$ \dfrac{ P(0) \quad \forall i \in \mathbb{N}. P(i) \Rightarrow P(i+1) }{ \forall n \in \mathbb{N}. P(n)} $$ just taken for ...
11
votes
4answers
4k views

How does backwards induction work to prove a property for all naturals?

I was reading a blogpost here: http://mzargar.wordpress.com/2009/07/19/cauchys-method-of-induction/ One thing that threw me off was that after the first four large displayed equations, there is the ...
22
votes
3answers
680 views

A (probably trivial) induction problem: $\sum_2^nk^{-2}\lt1$

So I'm a bit stuck on the following problem I'm attempting to solve. Essentially, I'm required to prove that $\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} < 1$ for all $n$. I've been toiling ...
17
votes
12answers
4k views

Prove that $ n < 2^{n}$ for all natural numbers $n$.

Prove that $ n < 2^{n} $ for all natural numbers $n$. I tried this with induction: Inequality clearly holds when $n=1$. Supposing that when $n=k$, $k<2^{k}$. Considering $k+1 <2^{k}+1$, ...
4
votes
2answers
10k views

Proving by induction that $ \sum_{k=0}^n{n \choose k} = 2^n$

Prove by induction that for all $n \ge 0$: $${n \choose 0} + {n \choose 1} + ... + {n \choose n} = 2^n.$$ In the inductive step, use Pascal’s identity, which is: $${n+1 \choose k} = {n \choose k-1} ...
4
votes
4answers
3k views

Proving the sum of the first $n$ natural numbers by induction [duplicate]

I am currently studying proving by induction but I am faced with a problem. I need to solve by induction the following question. $$1+2+3+\ldots+n=\frac{1}{2}n(n+1)$$ for all $n > 1$. Any ...
8
votes
5answers
2k views

Geometric mean never exceeds arithmetic mean

This was a mathematical induction question proposed in a textbook, and I've exhausted multiple approaches (proving RHS - LHS > 0, splitting the fraction, fractional exponents, etc.) The geometric ...
3
votes
4answers
129 views

Prove by mathematical induction that: $\forall n \in \mathbb{N}: 3^{n} > n^{3}$

Prove by mathematical induction that: $$\forall n \in \mathbb{N}: 3^{n} > n^{3}$$ Step 1: Show that the statement is true for $n = 1$: $$3^{1} > 1^{3} \Rightarrow 3 > 1$$ Step 2: Show ...
2
votes
5answers
4k views

Prove by mathematical induction that $2n ≤ 2^n$, for all integer $n≥1$?

I need to prove $2n \leq 2^n$, for all integer $n≥1$ by mathematical induction? This is how I prove this: Prove:$2n ≤ 2^n$, for all integer $n≥1$ Proof: $2+4+6+...+2n=2^n$ $i.)$ Let $P(n)=1 ...
25
votes
7answers
8k views

Is there no solution to the blue-eyed islander puzzle?

Text below copied from here The Blue-Eyed Islander problem is one of my favorites. You can read about it here on Terry Tao's website, along with some discussion. I'll copy the problem here as ...
46
votes
2answers
3k views

Proof of 1 = 0 by Mathematical Induction on Limits?

I got stuck with a problem that pop up in my mind while learning limits. I am still a high school student. Define $P(m)$ to be the statement: $\quad ...