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 ...
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$ ...
11
votes
4answers
549 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
3
votes
5answers
3k 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 ...
9
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 ...
5
votes
3answers
235 views

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 ...
1
vote
1answer
1k 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
712 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 ...
18
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: ...
9
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. ...
3
votes
5answers
306 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 ...
2
votes
5answers
2k 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: $$ ...
30
votes
17answers
6k 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$ ...
44
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 ...
20
votes
5answers
790 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? ...
10
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}}$$ ...
1
vote
2answers
683 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
530 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
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
750 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
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
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
184 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$.
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 ...
5
votes
2answers
993 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} = ...
4
votes
2answers
237 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 ...
0
votes
2answers
684 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
150 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 ...
18
votes
6answers
5k 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
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
741 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
320 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
362 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
708 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
7k 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
3k 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 = ...
6
votes
2answers
1k views

Vandermonde determinant by induction

The determinant at the top-left of the page can be done by induction, it says show that. I have done this before, if I submit this will I get marks? MORE IMPORTANTLY how do I do it by induction? The ...
5
votes
2answers
181 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
140 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
618 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
486 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$.
28
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 ...
16
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$, ...
13
votes
2answers
464 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.
13
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$, ...
11
votes
11answers
10k 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
5answers
571 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
3answers
657 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 ...