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

6
votes
2answers
124 views

If $x+\frac{1}{x}$ is a natural number, then $x^{n}+\frac{1}{x^{n}}$ is a natural number for all $n\in \mathbb{N}.$

I am trying to solve the following exercise. If $x+\frac{1}{x}$ is a natural number, then $x^{n}+\frac{1}{x^{n}}$ is a natural number for all $n\in \mathbb{N}.$ Here what I've done. If ...
1
vote
1answer
223 views

Induction Proof: Inequality involving Summation of Products with Squared Terms

I was trying to solve one of the bounty questions (yes i know it is very ambitious for a newbie like me:-) ). But regardless of my analysis being correct or incorrect, another problem originated from ...
-2
votes
3answers
1k views

Induction principle for verifying divisibility

I am stuck on one question: Show that $8^n-3^n$ is divisible by $5$. Thank you
0
votes
1answer
310 views

n number of cans on a circular track will traverse a car around it

The problem The sides of a circular track contain a sequence of cans of gasoline. The total amount in the cans is sufficient to enable a certain car to make one complete circuit of the track, and it ...
1
vote
3answers
407 views

Proof by Induction: Solving $1+3+5+\cdots+(2n-1)$

The question asks to verify that each equation is true for every positive integer n. The question is as follows: $$1+ 3 + 5 + \cdots + (2n - 1) = n^2$$ I have solved the base step which is where ...
1
vote
1answer
86 views

Question on induction proof (about direct sums of irreducible submodules)

Let $V$ be an $L$-module. I want to show that $V$ is a direct sum of irreducible $L$-submodules if each $L$-submodule of $V$ possesses a complement. I want to show this via induction on the dimension ...
0
votes
2answers
95 views

Proof by Induction (concerning $3^n\ge1+2n$)

I've been able to follow the idea and steps of induction so far but I've hit a road block in understanding one of the examples in a text book. This is what the book says p.97: Prove: $3^n \geq1 + 2n$ ...
2
votes
2answers
102 views

Proving that there are infinitely many Pythagorean quadruples by induction using described method

I want to prove that there are infinitely many Pythagorean quadruples by induction, using the following pattern: $1^2+2^2+2^2=3^2$ So I take $d=3$ and I want to prove by induction that I can form ...
2
votes
0answers
151 views

Prove by induction that 3 divides $n^3+2n$ [duplicate]

Possible Duplicate: Proof that $n^3+2n$ is divisible by 3 How can I prove by induction that for any positive integer $n$, $(n^3 +2n)$ is divisible by $3$?
-1
votes
0answers
80 views

Prove by induction for all integers [duplicate]

Possible Duplicate: Prove by induction I am stuck with my maths assignment. I need to prove for all integers $n\geq 1$ $$\sum_{i=1}^{n}(3i-1)^2=\frac{1}{2}n(6n^2+3n-1)\;.$$
1
vote
0answers
220 views

Prove the inequality $n! > 2^n$ by induction. [duplicate]

Possible Duplicate: Proof the inequality $n! \geq 2^n$ by induction Prove By Induction that $n!>2^n$ I have to prove the inequality $n! > 2^n$ for all integers $n \geq4$. I am ...
3
votes
5answers
8k views

Prove By Induction that $n!>2^n$ [duplicate]

Possible Duplicate: Proof the inequality $n! \geq 2^n$ by induction Prove by induction that $n!>2^n$ for all integers $n\ge4$. I know that I have to start from the basic step, which is ...
2
votes
4answers
857 views

Prove by induction (formula for $\sum^n(3i-1)^2$)

Anyone knows how to do this? The answer I'm getting is not correct. Prove by induction that, for all integers $n\ge1$, $$\sum_{i=1}^n (3i-1)^2 = \frac12 n(6n^2 + 3n - 1). $$ Thanks This Is what I ...
3
votes
1answer
143 views

Why do $\omega$-models of subsystems of $\mathsf{Z}_2$ satisfy full induction?

Richard Shore, in his 2010 paper in the Bulletin of Symbolic Logic, 'Reverse Mathematics: The Playground of Logic', writes that Obviously, if an $\omega$-model $\mathcal{M}$ (those with $M = ...
2
votes
1answer
746 views

Induction proof concerning number of leaves in a heap

I have a question about one of my homework assignments. I have to prove the following: Prove by induction that a heap with $n$ vertices has exactly $\lceil \frac{n}{2} \rceil$ leaves. This is ...
1
vote
2answers
882 views

prove a monotonically increasing function from recurrence relation by induction

How to prove $T(n)$ is a monotonically increasing function by induction provided that $T(n) = T(n/2 + \sqrt{n}) + \sqrt{6046}$? $n$ is larger than $n/2 + \sqrt{n}$ when $ n \geq 5$ and it is ...
3
votes
3answers
164 views

Confusion from a textbook comment about induction

I am teaching myself discrete math from this text: http://www.amazon.com/Discrete-Mathematics-Applications-Susanna-Epp/dp/0495391328/ In chapter 5 there is an example of mathematical induction, and ...
3
votes
2answers
2k views

Strong Induction proofs done with Weak Induction

I've been told that strong induction and weak induction are equivalent. However, in all of the proofs I've seen, I've only seen the proof done with the easier method in that case. I've never seen a ...
2
votes
6answers
334 views

Use mathematical induction to prove that for all integers $n \ge 2$, $2^{3n}-1$ is not prime

I had a homework due yesterday with this problem. The TA did the problem last week in discussion but I didn't understand it. She pulled out a $7k$ almost immediately, and I have no idea from where. ...
1
vote
1answer
136 views

Cardinality and ordinary mathematical induction

How do I approach this problem using ordinary mathematical induction? Notation: If A and B are sets then we will say they are the same cardinality and write $A\approx B$ if there is a one-to-one and ...
5
votes
2answers
469 views

Is this the correct way to perform mathematical induction? (re: derivative of $z^n$ is $nz^{n-1}$)

Here's a question: Derive $$\frac{\mathrm{d}}{\mathrm{d}z} z^n = nz^{n-1},$$ when n is a positive integer by using mathematical induction and and the derivative of a product of two functions ...
1
vote
2answers
151 views

Why does the expression of Peano induction has to be second order?

I'm reading the Stanford Encyclopedia of Philosophy entry on Second-order and Higher-order Logic. In it, I read the following: [W]e can express the Peano induction postulate by a second-order ...
1
vote
8answers
614 views

Mathematical induction question: why can we “assume $P(k)$ holds”?

So I see that the process for proof by induction is the following (using the following statement for sake of example: $P(n)$ is the formula for the sum of natural numbers $\leq n$: $0 + 1 + \cdots ...
3
votes
5answers
204 views

An expression of $1\cdot2 + 2\cdot3 + \cdots + n\cdot(n+1)$

I got a question in my homework, which is: Find the following sum and prove your claim: $$1\cdot2 + 2\cdot3 + 3\cdot4 + \cdots + n\cdot(n+1).$$ I want to prove this by mathematical ...
7
votes
2answers
210 views

Inductive proof that $(m!^n)n! \mid (mn)!$

I have worked this problem out before but am stuck on the inductive step. Show that $(m!^n)n! \mid (mn)!$ I am using induction on $n$. I thought to factor $(m(n+1))$! but can't get it ...
4
votes
1answer
1k views

Proving the Schwarz Inequality for Complex Numbers using Induction

I want to prove the following version of the Schwarz Inequality for complex numbers $a_1, a_2, \ldots, a_n \in \mathbb{C}$ and $b_1, b_2, \ldots, b_n \in \mathbb{C}$: $$|\sum_{j=1}^n a_j ...
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 ...
1
vote
1answer
550 views

Inductive proof of Cauchy's inequality for complex numbers?

I'm trying to put together an inductive proof of Cauchy's inequality for the complex case, $$ \left|\sum_{i=1}^na_ib_i\right|^2\leq\sum_{i=1}^n|a_i|^2\sum_{i=1}^n|b_i|^2. $$ The base case is easy, ...
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
5answers
804 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
203 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 ...
14
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
159 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
7answers
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
377 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
690 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
315 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 ...
4
votes
2answers
788 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
691 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
470 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
223 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
120 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
372 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 ...