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

4
votes
5answers
810 views

Mathematical induction equation involving a sum of binomial coefficients

I have a problem with a mathematical equation. I don’t find the given solution. This is the equation: $\sum\limits_{k=2}^{n-1} {k \choose 2} = {n \choose 3} $ I should show with induction that the ...
3
votes
3answers
3k views

Mathematical Induction and “the product of odd numbers is odd”

I am extremely poor at proofs and logical manipulation so I am stuck on a lot of these questions especially induction. The question below I have been stuck at for a little over 1 hour and I can't ...
0
votes
5answers
135 views

How can i solve a complex induction exercise? (formula for sum of fourth powers)

I have an induction exercise: It is $n \in \mathbb{N_0}$. Show: $$ \sum\limits_{k=1}^{n} k^4 = \frac 1 {30} n(n+1)(2n+1)(3n^2+3n-1) $$ As far as is understand it, you have to put in $(n+1)^4$ at ...
3
votes
2answers
210 views

Can this be solved by induction? (number of ways of cutting a rod into pieces)

I am reading an algorithm example. The example is about Rod cutting. The idea is that a steel rod can either be sold as it is, or be cut into integral pieces and ...
15
votes
5answers
2k views

Why doesn't induction extend to infinity? (re: Fourier series)

While reading some things about analytic functions earlier tonight it came to my attention that Fourier series are not necessarily analytic. I used to think one could prove that they are analytic ...
2
votes
2answers
162 views

Use induction to prove that $n^3 + (n+1)^3 + (n+2)^3 $ is divisible by $9$

Prove that for all integers $n\geq 0, n^3 + (n+1)^3 + (n+2)^3 $ is divisible by 9. If $ n=1, 1+8+27 = 36 = 9 * x $ Suppose $ n = k, k^3 + (k+1)^3 + (k+2)^3 $ is divisible by 9. Find out $ n = k + 1, ...
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 ...
55
votes
8answers
9k views

Surprise exam paradox?

I just remembered about a problem/paradox I read years ago in the fun section of the newspaper, which has had me wondering often times. The problem is as follows: A maths teacher says to the class ...
2
votes
1answer
2k views

Prove that in a bit string, the string 01 occurs at most one more time than the string 10.

Good morning. This is my first question in a StackExchange forum. Let me know if I'm doing anything incorrectly (posting in the wrong forum, etc.). Prove that in a bit string, the string 01 occurs at ...
0
votes
3answers
399 views

Proving by mathematical induction: $1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+…+\frac{1}{\sqrt{n}}>2(\sqrt{n+1}-1)$ [duplicate]

Possible Duplicate: Proof of an inequality: $\sqrt{n} < \frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \cdots + \frac{1}{\sqrt{n}}$ Proving ...
5
votes
3answers
705 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. ...
1
vote
1answer
320 views

Infinite induction “valid”

As you may know, induction works only when we have a statement involving natural numbers. For instance, For every $n$, the intersection of $n$ open sets is open. Now, the corresponding statement for ...
5
votes
2answers
805 views

Proof of Product Rule for Derivatives using Proof by Induction

I am trying to understand the proof of the General Result for the Product Rule for Derivatives by reading this. Relevant parts are as follows: Basis for the induction $$ D_x \left({f_1 ...
2
votes
3answers
706 views

Is this a proper use of induction? ($(n^2+5)n$ is divisible by 6)

Just want to get input on my use of induction in this problem: Question. Use mathematical induction to prove that $(n^2+5)n$ is divisible by $6$ for all integers $n \geqslant 1$. Proof by ...
2
votes
2answers
105 views

Proof that $7n+3 \leq 2^n$ for all $n\geq6$

Hows my proof look? Any feedback welcome
4
votes
2answers
478 views

How do I prove $(1 + \frac{1}{n})^n < n$ by mathematical induction?

$\displaystyle(1 + \frac{1}{n})^n < n$ for $n \gneq 3$ yes for $n = 1$ it is true I assume it is true for $n = k$ and get $\displaystyle(1+\frac{1}{k})^k < k$ I then go to $\displaystyle(1 ...
1
vote
2answers
60 views

How to prove $k^n \equiv 1 \pmod {k-1}$ (by induction)?

How to prove $k^n \equiv 1 \pmod {k-1}$ (by induction)?
4
votes
2answers
224 views

Proof of $(2n)!/(n!)^2\le2^{2n}$ by mathematical induction?

How do I approach this problem using mathematical induction? $$\frac{(2n)!}{(n!)^2} \leq 2^{2n}$$
0
votes
1answer
121 views

Algebra on $\binom{k+1}{i} = \binom{k+1}{0} + \binom{k+1}{1} + \cdots + \binom{k+1}{k} + \binom{k+1}{k+1}$ [duplicate]

Possible Duplicate: Algebraic Proof that $\sum\limits_{i=0}^n \binom{n}{i}=2^n$ I am trying to prove $\sum \limits_{i=0}^n \binom{n}{i} = 2^n$ by induction. I've been all over the net ...
3
votes
2answers
152 views

Prove by induction that $2^1+2^2+2^3+2^4+ \cdots +2^n=2(2^n-1)$

Alright I have this problem, Prove by induction $2^1+2^2+2^3+2^4+ \cdots +2^n=2(2^n-1)$ Now I've done this so far: Base case $n=1$: $$2^1 = 2$$ $$2(2^1-1)=2(2-1)=2(1)=2 .$$ Assume for $k$, prove ...
0
votes
2answers
376 views

What induction hypothesis do they mean? (Proof of the Division Theorem)

I'm reading, but I can't get what induction hypothesis they are talking about on page 10 on http://www.win.tue.nl/~hansc/vena/webalt.pdf at ...
1
vote
2answers
711 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 ...
7
votes
3answers
215 views

Proving $\frac{n^n}{3^n} < n! < \frac{n^n}{2^n}$ holds by induction

I am Computer Science person, and I'm trying to beef up my mathematical skills a little bit. This isn't homework and I don't have a professor I can go to to ask for help. I hope this is an ...
7
votes
4answers
1k views

Proof by Induction: Alternating Sum of Fibonacci Numbers [duplicate]

Possible Duplicate: Show that $f_0 - f_1 + f_2 - \cdots - f_{2n-1} + f_{2n} = f_{2n-1} - 1$ when $n$ is a positive integer This is a homework question so I'm looking to just be nudged in ...
0
votes
2answers
257 views

Induction and Integral Question (sum of 5th powers, integral of $x^5$)

I am quite lost on this question: (a) For $n\in \mathbb{N}$, use induction to show that $$\sum_{k=1}^{n}k^{5}=\frac{2n^{6}+6n^{5}+5n^4-n^2}{12}$$ (b) Fix $b>0$. Use the definition of ...
1
vote
2answers
120 views

find the total Q

hello i have a problem with exercise the problem is follow: Consider the set $Q$ of integers defined as follows: $1 ∈ Q$ If $b ∈ Q$, then $2b-1 ∈ Q$ If $b ∈ Q$, then $2b +1 ∈ Q$ What is the total ...
1
vote
3answers
123 views

Finite set cardinality decreasing

Say I have a finite set $A$ and know its cardinality. How can I prove that, by repeatedly applying some algorithm, which removes a known number of elements from $A$ each time, its cardinality will ...
1
vote
0answers
72 views

In a semigroup $S=\{a_1, \ldots, a_n\}$, any product $a_1 * \ldots * a_i, 1 \le i \le n$ is unique [duplicate]

Possible Duplicate: How does one actually show from associativity that one can drop parentheses? Claim: Let $(S, *)$ be a semigroup and $a_1, \ldots, a_n \in S$. Then $a_1 * \ldots * a_n$ ...
2
votes
2answers
105 views

A question on mathematical Induction: $f(a)=f(a^2)$ implies $f(a)=f(a^{2^n})$

I came across this question in an answer given to a question here on MSE. Given that $f(a)=f(a^2)$ for all $a\in [0,1]$,$f$ continuous, it is easy to prove by induction that $p(n): f(a) = ...
2
votes
1answer
61 views

Proving $a_{n+1}=1-e^{-a_n}$ has no lower bound if $a_1<0$

As the title states, I'm trying to prove $a_{n+1}=1-e^{-a_n}$ has no infimum if $a_1<0$. I'm not sure this is true, but calculating $a_n$ for large $n$ leads me to believe it is. I've already ...
1
vote
2answers
159 views

Prove that $2^n | P(2n, n)$

I am attempting to use Induction to prove this, but I am not sure if it is the right method to take. Here is what I have tried: Induction Hypothesis: Assume $P(k)$ is true for some fixed $ k \geq 1$ ...
0
votes
2answers
109 views

Induction on a Sequence

This is a homework question that I am trying to use induction to solve. I am having a bit of trouble finishing the proof out: Suppose $0 < k < 1$ and for each $n \in N$, $\langle x_n \rangle$ ...
1
vote
2answers
140 views

$2+4+6+\cdots+2n=n^2+n$ by mathematical induction

I am trying to prove $2+4+6+\cdots +2n=n^2+n$ by mathematical induction. I followed all the steps and the $P_{k+1}$ was $2+4+6+\cdots+2(k+1)=(k+1)^2+k+1$ Starting from the left hand side of the ...
4
votes
3answers
234 views

Proving $n! > n$ for $n > 2$ using mathematical induction

I have to prove $n<n!$ for all $n>2$ by mathematical induction. I did it as follows. I proved the base case. Then let it be true for $K>2$: $$ K<K! $$ I have to prove, $$ ...
2
votes
1answer
249 views

Inductive riddles for homework

we got two inductive riddles for homework. I need a hint to get me started. So the first one is related to the Fibonacci numbers: Let ‫‪Dn‬‬ be the number of possible ways to cover a table of size ...
2
votes
1answer
114 views

Proof for $\sqrt[n]{n!}\le{{n+1}\over2}$ using induction

Prove $\sqrt[n]{n!}\le{{n+1}\over2}$, $n \in N^+$, using induction. This is how far I got, but then I got stuck: $$\sqrt[n+1]{(n+1)!}\le{{n+2}\over2}$$ $$((n+1)!)^{1\over{n+1}}\le{n\over2}+1$$ ...
1
vote
2answers
465 views

Using induction to prove propositions involving exponents of x

I am working on a chapter on mathematical induction. I came across a problem which seemed relatively simple, but I was unable to prove. My understanding of inductions is that if you have the equation ...
3
votes
3answers
697 views

Prove by induction: $2^n + 3^n -5^n$ is divisible by $3$

Let $P(n) = 2^n + 3^n - 5^n $. I want to prove that $P(n)$ is true for all integers $n\geq 1$. The basis step for this proof is easy enough: $P(1)$ is divisible by $3$. For the inductive step, I ...
1
vote
4answers
146 views

False statement proven by induction?: $ n\geq a\Rightarrow n!\geq a^n, n\in \mathbb{N}-\left \{ 0 \right \}$

Can you spot my mistake? I will show the false statement, that $n\geq a\Rightarrow n!\geq a^n, n\in \mathbb{N}-\left \{ 0 \right \}$, with induction For $n=1$ , $1\geq a\Rightarrow 1!\geq ...
4
votes
5answers
553 views

Proving that $f(n)$ is an integer using mathematical induction

I want to prove that $$\frac{n^3}{3}+\frac{n^5}{5}+\frac{7 n}{15}$$ is an integer for every integer $n \geq 1$. I define P(n) to be: $$\frac{n^3}{3}+\frac{n^5}{5}+\frac{7 n}{15}$$ is an integer. ...
11
votes
10answers
328 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
1answer
58 views

Prove that $x_{n} = (n^{2}(n+1)^{2})/4$ via complete induction for the sequence $x_{n+1}=x_{n} + (n+1)^3$

The sequence is described by $x_{n+1}=x_{n} + (n+1)^3$. Prove that $x_{n} = (n^{2}(n+1)^{2})/4$ via complete induction. I actually have two questions. I'm a bit lost as to how to start the induction ...
3
votes
3answers
530 views

Strong Mathematical Induction Recursion Inequality

I have a question that is for a homework assignment and I just would like to ask if I seem to be on the right track or if I'm just doing it completely wrong. Here is the question: The sequence ...
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 ...
7
votes
4answers
176 views

$n! \leq \left( \frac{n+1}{2} \right)^n$ via induction

I have to show $n! \leq \left( \frac{n+1}{2} \right)^n$ via induction. This is where I am stuck: $$\left( \frac{n+2}{2} \right)^{n+1} \geq \dots \geq =2 \left( \frac{n+1}{2} \right)^{n+1} = ...
5
votes
2answers
564 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 ...
3
votes
1answer
133 views

Mathematical induction usage

I have a question on Mathematical Induction. Ok, when we are presented let's take a concrete example, with a sum of finite numbers and say we want to prove a result, e.g. that: $$ S_n = 1 + 4 + 9 ...
1
vote
2answers
666 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}$$
1
vote
2answers
103 views

Proof of inequality with induction

I have to show that $\prod_{k=1}^n(1+a_k) \geq 1 + \sum_{k=1}^n a_k$ is valid for all $1 \leq k \leq n$ using the fact that $a_k \geq 0$. Showing that it works for $n=0$ was easy enough. Then I tried ...
2
votes
2answers
160 views

Peano, simple induction

I have the axiom from Peano's axioms: If $A\subseteq \mathbb{N}$ and $1\in A$ and $m\in A \Rightarrow S(m)\in A$, then $A=\mathbb{N}$. My book tells me that it secures that there are no more natural ...