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

1
vote
4answers
780 views

Induction Proof: $5^n + 5 < 5^{n+1}$

I am trying to prove for all natural $n$ that: $$5^n + 5 < 5^{n+1}$$ I did the basic step with $n=1$ and inequality holds, I am now at the induction step: $$5^{k+1} + 5 < 5^{k+2}$$ and I have ...
6
votes
2answers
13k views

Proving Inequalities using Induction

I'm pretty new to writing proofs. I've recently been trying to tackle proofs by induction. I'm having a hard time applying my knowledge of how induction works to other types of problems (divisibility, ...
4
votes
1answer
265 views

Ackermann-Péter Function: Proof by induction that A(x,y) < A(x,y+1)

Let $$\begin{eqnarray*} A(0,y) &=& y+1 \\ A(x+1,0) &=& A(x,1) \\ A(x+1,y+1) &=& A(x,A(x+1,y)) \end{eqnarray*}$$ I want to prove by induction over x that $$A(x,y) < ...
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 ...
2
votes
3answers
116 views

Proving that an expression divides a number

How do you prove that $$n(n+1)(n+2)$$ is divisible by 6 by using the method of mathematical induction? According to my book $$\begin{aligned} (n+1)(n+2)(n+3) &= n(n+1)(n+2)+3(n+1)(n+2)\\ &= ...
1
vote
3answers
123 views

Find the value of a succession of additions

$$1^2+2^2+3^2+...+10000$$ How do you find the exact value of that? I'm studying induction, and I'm still not sure how to get that value.
0
votes
0answers
42 views

Prove by Induction that the Hyper graph $Q_d$ has at least $2^{{2^d} - d - 2}$ spanning trees

we experimented with some pen and paper and saw that the maximal number of spanning trees can be recursively defined as: $Q(1) = 1$ $Q(2) = 4$ $Q(d) = Q(d-1) * 2^{d-1}$ for $Q_d \geqslant 1$ ...
3
votes
4answers
318 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 ...
2
votes
1answer
2k views

Induction for sum of Poisson distributed random variables

Given the identically distributed and independant random variables $X_1,X_2,\ldots\sim\operatorname{Po}(\lambda)$ and $S_n=X_1+\ldots+X_n$ show with induction that ...
1
vote
1answer
159 views

Prove that if $n \in \mathbb{N}$, $n\ge 1$

As the title says. I encounter this problem in Bernd Schroeder's book of "Mathematical Analysis: A Concise Introduction", p.15. It essentially characterizes natural number from the axioms regarding ...
4
votes
1answer
189 views

Generating function of Lah numbers

Let $L(n,k)\!\in\!\mathbb{N}_0$ be the Lah numbers. We know that they satisfy $$L(n,k)=L(n\!-\!1,k\!-\!1)+(n\!+\!k\!-\!1)L(n\!-\!1,k)$$ for all $n,k\!\in\!\mathbb{Z}$. How can I prove ...
4
votes
0answers
111 views

Transfinite induction and valuation rank

In Engler's valued fields, exercise 3.5.2 goes as follows Construct valuations on $\Bbb{C}$ of rank $\kappa$ for every cardinal $\kappa \leq 2^{\aleph_0}$. The idea behind this (for any ...
2
votes
2answers
172 views

$\wp^{(\omega)}(A)=?$

Let $A$ be a set, $$\wp^{(0)}(A)=A$$ $$\wp^{(n+1)}(A)=\wp(\wp^{(n)}(A))$$ But what sense does $\wp^{(\alpha)}(A)$ make where $\alpha$ is a limit ordinal number? The most natural way is let ...
3
votes
3answers
250 views

Proving that $S_n$ has order $n!$

I have been working on this exercise for a while now. It's in B.L. van der Waerden's Algebra (Volume I), page $19$. The exercise is as follows: The order of the symmetric group $S_n$ is ...
2
votes
0answers
173 views

Group-theoretic proof that an increasing multiplicative function is exponential

Let $f:\mathbb{N}\rightarrow\mathbb{N}$ be a strictly increasing function such that $$f(2)=2$$ and $$f(mn)=f(m)f(n)$$ for all positive integers $m,n$ such that $$\gcd(m,n)=1$$ Prove that ...
8
votes
5answers
368 views

Prove that $4^{2n} + 10n -1$ is a multiple of 25

Prove that if $n$ is a positive integer then $4^{2n} + 10n - 1$ is a multiple of $25$ I see that proof by induction would be the logical thing here so I start with trying $n=1$ and it is fine. Then ...
0
votes
2answers
88 views

Explain a statement about math induction base.

I was reading an article in wikipedia about math induction: http://en.wikipedia.org/wiki/Mathematical_induction And there is a sentence: "Note that the first quantifier in the axiom ranges over ...
3
votes
3answers
334 views

Statements true for all integers but not provable by induction

Is there any examples of statements P(n) such that "for all $n>1$, P(n)" is provable, but P(n)=>P(n+1) is not provable? (without using some mild deformation of "for all $n>1$, ...
7
votes
1answer
718 views

How to prove that $\mathrm{Fibonacci}(n) \leq n!$, for $n\geq 0$

I am trying to prove it by induction, but I'm stuck $$\mathrm{fib}(0) = 0 < 0! = 1;$$ $$\mathrm{fib}(1) = 1 = 1! = 1;$$ Base case n = 2, $$\mathrm{fib}(2) = 1 < 2! = 2;$$ Inductive case ...
2
votes
3answers
131 views

Proof $\sum\limits_{r=1}^{n} r >\frac{1}{2}n^2$ using induction

Question: $$\text{Prove by induction that, for all integers } n, n \geq 1:$$ $$\sum\limits_{r=1}^{n} r >\frac{1}{2}n^2$$ Working: Step 1 (Prove true for n=1): $$1>\frac{1}{2}(1)^2$$ ...
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
9answers
310 views

How to show that $n(n^2 + 8)$ is a multiple of 3 where $n\geq 1 $ using induction?

I am attempting a question, where I have to show $n(n^2 + 8)$ is a multiple of 3 where $n\geq 1 $. I have managed to solve the base case, which gives 9, which is a multiple of 3. From here on, I ...
4
votes
3answers
529 views

Why does induction prove equality?

I know how to prove equality for my homework assignment, but I can't understand why it actually proves that equality. Could you please explain?
4
votes
1answer
172 views

Prove by induction $\sum_{i=0}^n i(i+1)(i+2) = (n(n+1)(n+2)(n+3))/4$

Anyone knows how to do this? I'm having trouble after the following step: Prove by induction that $\sum_{i=0}^n i(i+1)(i+2) = (n(n+1)(n+2)(n+3))/4$ Thanks $((n(n+1)(n+2)(n+3))/4) + (n+1)(n+2)(n+3)$ ...
5
votes
2answers
464 views

Odd Binomial Coefficients?

By Newton's Formula: $$(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k}b^k $$ Proof that every $\dbinom{n}{k}$ is odd if and only if $n=2^r-1$. I have already shown that if $n$ is of the form $2^r-1$, ...
5
votes
1answer
445 views

Proof that ${2}^{3n+2}+{5}^{n+1}\text { is divisible by 3}$ using induction

I am having trouble with a proof by induction exercise. My book shows the typical steps for proving divisibility induction with the number 3 lets say are as following: Prove true for $n=1$ Assume ...
3
votes
2answers
274 views

Lower Bound of Central Binomial Coefficients

I would like to prove by induction the following inequality: $\frac{4^n}{n+1} < \binom{2n}{n}$, for all natural numbers n > 1. Any hints?
6
votes
1answer
324 views

Backwards induction to show that $x_1\cdots x_n \leq ((x_1+\cdots+x_n)/n )^n$

This question is from "Concrete Mathematics", by Knuth. Sometimes it's possible to use induction backwards, proving things from $n$ to $n-1$ instead of vice versa! For example, consider the ...
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$ ...
2
votes
2answers
232 views

Solving Induction $\prod\limits_{i=1}^{n-1}\left(1+\frac{1}{i}\right)^{i} = \frac{n^{n}}{n!}$

I try to solve this by induction: $$ \prod_{i=1}^{n-1}\left(1+\frac{1}{i} \right)^{i} = \frac{n^{n}}{n!} $$ This leads me to: $$ \prod_{i=1}^{n+1-1}\left(1+\frac{1}{i}\right)^{i} = ...
4
votes
1answer
82 views

Is my proof for $\sum_{i=1}^{n}x_{i}y_{i}\leq \sqrt{\sum_{i=1}^{n}x_{i}^{2}\sum_{i=1}^{n}y_{i}^{2}}$ correct?

Is this part of my proof by induction correct ? $\sum_{i=1}^{n}x_{i}y_{i}\leq \sqrt{\sum_{i=1}^{n}x_{i}^{2}\sum_{i=1}^{n}y_{i}^{2}}$ this is true when the true is that : $\sum_{i=1}^{n}\left ...
1
vote
1answer
394 views

Proof by induction of triangle inequality in Hilbert space.

I've made proof by induction over $n$ for triangle inequality : $\left \| x+y \right \|_{e}\leq \left \| x \right \|_{e}+\left \| y \right \|_{e}$ ,where $\left \| x \right ...
2
votes
6answers
151 views

How can I show using mathematical induction that $\frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2^n} = \frac{2^n - 1}{2^n}$

How can I show using mathematical induction that $\frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2^n} = \frac{2^n - 1}{2^n}$ Edit: I'm specifically stuck on showing that $\frac{2^n - 1}{2^n} + ...
1
vote
1answer
718 views

Prove by induction that $n^3 > n^2 − 6n + 4$ for all $n ∈ {\mathbb N}$ with $n ≥ 1$ .

Would you please check if my answer is correct and confirm that it is proof by induction? Thank you. The proof is by induction. Base Case: when $n=1$: ...
6
votes
3answers
165 views

Induction Proof and divisibility by $2^n$

I'm trying to use induction to prove that for every integer $n > 0$ there exists an $n$-digit integer A(n) that is divisible by $2^n$ and that consists entirely of digits “1” and “2”. Does anyone ...
1
vote
1answer
895 views

Inductive Proof of a countable set Cartesian product [duplicate]

Possible Duplicate: Proving $\mathbb{N}^k$ is countable I would like to prove that if S is countable then for any positive integer n the set $S^n$ (the n-fold Cartesian product of S with ...
1
vote
1answer
69 views

Prove that L($G^R$) = $(L(G))^R$

I'm stuck with this exercise from a course in formal languages that I am taking. Could someone help me with this? Big thanks! For any w, define $w^R$ as $\lambda ^R \text{ = $\lambda $}$ ...
2
votes
2answers
599 views

set-theoretic function definition; recursion theorem

I am an undergraduate student, currently studying axiomatic set theory (I am reading Halmos' Naive Set Theory as an overview, and consulting other sources recommended to me to supplement the sparser ...
0
votes
2answers
2k views

I want a clear explanation for the Principle of Strong Mathematical Induction

I understood the Principle of Mathematical Induction. I know how to make a recursive definition. But I am stuck with how the "Principle of Strong Mathematical Induction (- the Alternative Form)" ...
4
votes
1answer
181 views

How does adding the full second order induction scheme affect the consistency strength of subsystems of second order arithmetic?

Following on from my question about $\omega$-models, I'm interested in the interaction between subsystems of second order arithmetic with restricted induction such as $\mathsf{RCA}_0$ and those which ...
0
votes
2answers
81 views

What is the most basic graph, and how would you use it in an induction-proof?

Can a single point be a graph? Or is it just a single edge and two vertices? How do you apply this to an induction-proof in graph-theory? thanks
1
vote
3answers
182 views

Difficulties in a proof by mathematical induction (2) [duplicate]

Possible Duplicate: proof by induction: n/(n+1) Continuing from here, I got a splendid answer that helped a lot. I'm tackling one now, but I've run into problems. Prove by mathematical ...
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( ...
2
votes
0answers
203 views

Examples of proofs by induction with respect to relations that are not strict total orders.

I have read this Wikipedia article and found it fascinating. I came across it after I tried to prove a certain statement with a method resembling induction in the set of natural numbers but ordered by ...
0
votes
1answer
702 views

Simple Nim game with equal-sized piles.

Consider the standard Nim game, i.e. you can take as many coins as you want from a single pile, you should take at least one coin and you can't take coins from two or more different piles at the same ...
5
votes
3answers
646 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 ...
1
vote
2answers
456 views

Prove via mathematical induction that $4n < 2^n$ for all $ n≥5$.

I did the following base case $n = 5$ $$\begin{align*} 4(5) &\lt 2 ^5\\ 20 &\lt 32 \end{align*}$$ So true. $$\begin{align*} 4n &\lt 2^n\\ n &\lt 2^{n-2}\\ \log_2(n)+2 ...
4
votes
1answer
1k views

(Inductive Proofs) Show why one inductive hypothesis works, and the other does not.

Here's a homework problem I have for my class about Discrete Mathematics: Suppose that we want to prove that $$\frac12\cdot\frac34\cdot\ldots\cdot\frac{2n-1}{2n} < \frac1{\sqrt{3n}}$$ ...
2
votes
1answer
150 views

Proving mathematical induction with arbitrary base using (weak) induction

I attempted a proof of mathematical induction using an arbitrary base case, but was unsuccessful (and hence this question). Below is what I was trying to do and along with my thinking; if anyone can ...
0
votes
3answers
162 views

How to prove $2^n < n!$ using Mathematical Induction? [duplicate]

Possible Duplicate: Proof the inequality $n! \geq 2^n$ by induction I have the following: Prove that for all $n \in Z^+,\space n > 3 \implies 2^n < n!$ Please provide the steps ...