Induction in general is the inference from the particular to the general. Mathematical induction is not true induction, but is a form of deductive reasoning. Its most common use is induction over well ordered sets, such as natural numbers, or ordinals. While induction can be expanded to class ...

learn more… | top users | synonyms

29
votes
5answers
2k 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 ...
10
votes
4answers
521 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
19
votes
5answers
3k 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$ ...
3
votes
5answers
2k 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 ...
51
votes
6answers
5k 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
4answers
2k 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...,k ...
1
vote
1answer
977 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 ...
8
votes
4answers
668 views

Induction Proof Help [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 = (x-y)(x^{n-1}+x^{n-2}y+\dots +xy^{n-2}+y^{n-1)}$$ $(x^n-y^n)/(x-y) =$ the ...
17
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: ...
3
votes
5answers
263 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 ...
29
votes
17answers
5k 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$ ...
43
votes
2answers
2k 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 ...
18
votes
5answers
749 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? ...
1
vote
2answers
662 views

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

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}$$
4
votes
3answers
451 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
1k views

Proof via Induction for A Summation

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: $$ ...
2
votes
5answers
2k 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 ...
1
vote
2answers
687 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 ...
5
votes
4answers
2k 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 ...
6
votes
4answers
183 views

Induction proof: $S$ contains powers of 2 and predecessors implies $S={\bf N}$

Let $S$ be a subset of $\mathbb{N}$ such that $$2^k\in S\quad\forall\ k\in\mathbb N$$ and, $$k\in S\Rightarrow k-1\in S\quad\forall\ k\ge2,k\in\mathbb N$$ Show by induction that $S=\mathbb N$.
9
votes
6answers
1k 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
2answers
2k 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 ...
4
votes
2answers
226 views

Representing Any $n \geq 4$ as a Sum of 2's and 5's

Use induction on $n$ to prove that for all integers $n\geq 4$, postage of $n$ cents can be realized using only $2$ cent and $5$ cent stamps. I thinks it is little bit different. How can I use ...
4
votes
2answers
957 views

How to prove $a^n < n!$ for all $n$ sufficiently large, and $n! \leq n^n$ for all $n$, by induction?

I have a couple things I want to prove. I'm pretty sure a proof by induction is the best route for these. First, I need to show that $5^n < n!$ from some $n_{0} > 0$. I'm choosing $n_{0} = ...
0
votes
2answers
606 views

Help with graph induction question?

Given a graph $G$ with $n$ vertices, where $n$ is even, prove by induction that if every vertex has degree $n/2 + 1$, then $G$ must contain a 3-cycle. A 3-cycle is a set of 3 vertices, $a; b; c$ such ...
0
votes
5answers
147 views

Prove by induction: $2^n = C(n,0) + C(n,1) + \cdots + C(n,n)$ [duplicate]

This is a question I came across in an old midterm and I'm not sure how to do it. Any help is appreciated. $$2^n = C(n,0) + C(n,1) + \cdots + C(n,n).$$ Prove this statement is true for all $n ...
17
votes
6answers
4k 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 ...
5
votes
2answers
5k views

Strong Mathematical Induction: Why More than One Base Case?

I am trying to understand this example of strong induction. I know normal induction. In normal induction, if base case is true then we assume some number $n$ to be true. Afterwards, we prove $n+1$ is ...
5
votes
5answers
1k views

Difficulties in a proof by mathematical induction (involves evaluating $\sum r3^r$).

Please help. I've been stuck on this for 2 days. Haven't found any easy explaining text. The question is : Prove by mathematical induction that : $$ \sum_{r=1}^n r3^r = \frac{3}{4} \left[ 3^n \left( ...
5
votes
3answers
683 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
4answers
314 views

Proving that there are infinite cardinal numbers >$\mathfrak{c}$

I was reading Simmons' book and he states that there are infinite cardinal numbers > $\mathfrak{c}$ where $\mathfrak{c}$ denotes the number of Real Numbers. For this, he states that we can construct ...
4
votes
3answers
335 views

Proof by induction or contradiction?

I have to prove that $(4k + 3) ^2 - (4k + 3)$ is not divisible by $4$. What would be the best approach for this, proof by induction or contradiction? I've tried both and haven't got very far. Any ...
3
votes
4answers
696 views

demonstration by induction: $(1+a)^n ≥1+an$

Demonstrate by induction: $(1+a)^n ≥1+an$ is true, given a real number $a$, for any $n ∈ \mathbb N$. With $a > 0$ I need to demostre this using the induction principle. My doubt is in the second ...
2
votes
2answers
6k views

Proof by induction: $2^n > n^2$ for all integer $n$ greater than $4$ [duplicate]

I am a CS undergrad and I'm studying for the finals in college and I saw this question in an exercise list: Prove, using mathematical induction, that $2^n > n^2$ for all integer n greater than ...
1
vote
3answers
2k views

Prove $(n^5-n)$ is divisible by 5 by induction.

So I started with a base case $n = 1$. This yields $5|0$, which is true since zero is divisible by any non zero number. I let $n = k >= 1$ and let $5|A = (k^5-k)$. Now I want to show $5|B = ...
5
votes
2answers
176 views

Number of bitstrings with $000$ as substring

I have $F_n$ number of bitstrings that have $000$, How would I prove that for $n \ge 4$ , $a_n = a_{n-1} +a_{n-2}+a_{n-3}+ 2^{n-3}$? Now there are many ways to go about this but if I choose starting ...
5
votes
4answers
1k 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 ...
2
votes
2answers
138 views

Proof of $(a+b)^{n+1}$

I have to do proof of $(a+b)^n$ and $(a+b)^{n+1}$ with mathematical induction. I finished the first one $(a+b)^n = a^n + na^{n-1}b+\dots+b^n$. I however have trouble with the second one, I don't ...
2
votes
4answers
517 views

For what natural numbers is $n^3 < 2^n$? Prove by induction

Problem For what natural numbers is $n^3 < 2^n$? Attempt @ Solution For $n=1$, $1 < 2$ Suppose $n^3 < 2^n$ for some $n = k \ge 1$ It looks like the inequality is true for $n = 0$, $n = 1$ ...
0
votes
5answers
407 views

Induction: Prove that $4^{n+1}+5^{2 n - 1}$ is divisible by 21 for all $n \geq 1$.

Induction: Prove that $4^{n+1}+5^{2 n - 1}$ is divisible by 21 for all $n \geq 1$.
27
votes
7answers
1k views

Must we use induction to prove a statement for all integers

This question is prompted by a remark from Bill Dubuque in his answer to this question on proving a particular sum without using mathematical induction. From Bill's answer: A proof that a ...
8
votes
6answers
2k 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. ...
15
votes
12answers
2k 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$, ...
12
votes
2answers
452 views

Prove $\sqrt{2\sqrt{3\sqrt{\cdots\sqrt{n}}}}<3$ by induction.

Problem: prove $\sqrt{2\sqrt{3\sqrt{\cdots\sqrt{n}}}}<3$ by induction. I tried some, but stopped in $\sqrt[2^n]{n+1}$. Also tried with $2\sqrt{3\cdots}<3^2$ and so on.
12
votes
2answers
3k views

What is complete induction, by example?

So, I've been revising for an exam and I came up against the question " prove $4(9^n) + 3(2^n)$ is divisible by 7 for all $n>0$. Now, I know how to do this. If I assume $n=k$ divisible by $7$, ...
10
votes
11answers
9k views

Proof that $n^3+2n$ is divisible by 3

I'm trying to freshen up for school in another month, and I'm struggling with the simplest of proofs! Problem: For any natural number n , n3 + 2n is divisible by 3. This makes sense ...
5
votes
3answers
635 views

Fake induction proof

Using the induction method: $(\forall P)[[P(0) \land ( \forall k \in \mathbb{N}) (P(k) \Rightarrow P(k+1))] \Rightarrow ( \forall n \in \mathbb{N} ) [ P(n) ]]$ Why this proof is wrong? $P(x)\equiv ...
5
votes
2answers
552 views

Using strong induction to get the AM-GM inequality for $2^n$ numbers

The arithmetic mean of $k$ numbers $a_1, a_2, \ldots, a_k$ is their average $\frac{a_1+a_2+\cdots+a_k}{k}=AM$. Their geometric mean is $\sqrt[k]{a_1a_2\cdots a_k}=GM$. I am asked to show this: Use ...
2
votes
3answers
1k views

How to use mathematical induction with inequalities?

I've been using mathematical induction to prove propositions like this: $$1 + 3 + 5 + \cdots + (2n-1) = n^2$$ Which is an equality. I am, however, unable to solve inequalities. For instance, this ...
0
votes
2answers
141 views

Is it possible to play the Tower of Hanoi with fewer than $2^n-1$ moves?

The Tower of Hanoi game consists of three identical upright pegs and n rings all of different diameters that can be stacked over any of the pegs. Initially, all of the rings are stacked around one of ...