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

2
votes
2answers
116 views

Prove that $n! < n^n $ where n >1 and is an integer , why do some people say my solution is wrong?

Prove that $n! < n^n $ where n >1 and is an integer. Lets skip the base case cause its trivial. Assume that: $$ k! < k^k = $$ Inductive step: $$(k+1)! < (k+1)^{k+1} =$$ $$(k)!(k+1) < ...
0
votes
1answer
82 views

Why is this summation formula wrong?

This is the alternate form of the summation formula: $$ \sum^{n}_{k=0} a(c)^k = \frac{ac^{n+1} - a}{c - 1} $$ so why is this wrong? $$ \sum^{n}_{k=0} (-\frac{1}{2})^k = \frac{(-\frac{1}{2})^{n+1} - ...
4
votes
6answers
97 views

Is $\sum_{i=1}^{n-1}i=\binom{n}{2}$?

How can I show that $$ \sum_{i=1}^{n-1}i=\binom{n}{2}? $$ This is what I have tried, but I do not know if it is correct: Proof. Let $n=2$. Then, $$ \begin{align} \sum_{i=1}^{1}i&=1\text{, ...
2
votes
1answer
265 views

Does mathematical induction assume that non-negative integers are infinite?

Does mathematical induction assume that the non-negative integers continue indefinitely? A friend of mine was attempting to show me that there are an infinite number of non-negative integers using ...
0
votes
2answers
33 views

recurrence relation with induction

The following recurrence relation: $T(n)=T(n-1)+n=1+\frac{n^2+n}{2}=\theta(n^2)$, so this mean that: there is $c_1, c_2, n_o > 0 : c_1n^2<=1+\frac{n^2+n}{2}<=c_2n^2$, the second inequality ...
1
vote
2answers
92 views

Prove by induction that $1^3 + 2^3 + 3^3 + …+ n^3= \frac{n^2(n+1)^2}{4}$ for all $n\geq1$. [duplicate]

Use mathematical induction to prove that $1^3 + 2^3 + 3^3 + .....+ n^3= \frac{n^2(n+1)^2}{4}$ for all $n\geq1$. Can anyone explain? Because I have no clue where to begin. I mean, I can show that ...
4
votes
1answer
315 views

Sum of alternating sign squares of integers stuck with proof by induction

Note that $$ A(1):1=1\\A(2):1-4=-(1+2)\\A(3):1-4+9=1+2+3\\A(4):1-4+9-16=-(1+2+3+4) $$ Let us set up the $A(k)$: $$ A(k)=1-4+9-…+(-1)^{k+1}k^2=(-1)^{k+1}(1+2+…+k) $$ Setting up $A(k+1)$: $$ ...
3
votes
4answers
94 views

Stuck with an inequality proof by induction

In Apostol's «Calculus I» on page 33 there is the following proof by induction: To prove: $$ 1^2+2^2+...+(n-1)^2<n^3/3<1^2+2^2+...+n^2 $$ Solution: Consider the leftmost iequality ...
1
vote
0answers
62 views

Trying to prove an identity about a product

I have a product formula that, given a tuple $(a_1, \dots, a_{n-1}, 0)$, computes a dimension (of a vector space) via the following formula: $$ \mathrm{dimension} = \prod_{i < j} {(a_i + \cdots + ...
6
votes
3answers
107 views

How to prove $4(n!)>2^{n+2}$ for $ n\geq 4$ with induction

I've done the base step, but how do I prove it is true for $n+1$ without using a fallacy? $$4(n!)>2^{n+2}\quad \text{for } n\geq 4$$ Please help.
4
votes
1answer
29 views

Multiplication function with sets

Prove there is a unique function $$* :\mathbb N \times \mathbb N\to\mathbb N$$ such that: $m * 0 = 0 $ for all $m \in \mathbb N$ $m * (n+1) = m * n + m$ for all $m,n \in \mathbb N$
1
vote
1answer
48 views

Some problems about the proof of a theorem

There's a theorem in my book (Complexity and cryptography by Talbot and Welsh, chapter 4) where I don't understand some parts of its proof: THEOREM: Suppose $f \in \mathbb Z[x_1,..., x_n]$ has ...
11
votes
3answers
344 views

Irrationality of $\sqrt 2$ using induction

I came upon this exercise in a textbook. I know that $\frac{n}{b} \ne \sqrt{2} $ for all $b \gt 0$ and $n \le N_0$. How can I then show that $\frac{N_0 + 1}{b} \ne \sqrt{2}$ for all $b \gt 0$?
1
vote
0answers
100 views

Proving by induction that $n^{n+1} > (n+1)^n$ for $n \ge 3$ [duplicate]

Prove the following inequality by mathematical induction: $$n^{n+1}>{(n+1)}^n \qquad (n\geq3)$$ Obviously it holds for $n=3$. Assume $P(n)$ holds, then $LHS=n^{n+1}$
7
votes
2answers
141 views

Power tower inequality

I want to prove the following power tower inequality: $$ 3 \uparrow \uparrow 100 > 4 \uparrow \uparrow 99 $$ but I don't know how to do this. I think that induction will not work, because I think ...
13
votes
6answers
404 views

Show that $n \ge \sqrt{n+1}+\sqrt{n}$

(how) Can I show that: $n \ge \sqrt{n+1}+\sqrt{n}$ ? It should be true for all $n \ge 5$. Tried it via induction: $n=5$: $5 \ge \sqrt{5} + \sqrt{6} $ is true. $n\implies n+1$: I need to show ...
0
votes
2answers
105 views

Two exercises on mathematical induction

Studying for a test and can't work out how to do two questions on the sample test. (1) Suppose a sequence of numbers $a_1$, $a_2$, $\dots$ is defined recursively by: $$a_1 = 1\qquad\text{and}\qquad ...
1
vote
2answers
811 views

Prove that $5^n - 2^n$ is divisible by $3$ for all nonnegative integers $n$ using mathematical induction [duplicate]

Using mathematical induction, prove for all integers n 1 that $5^n - 2^n$ is divisible by 3. Can someone help me with this?
8
votes
3answers
381 views

Inductively prove that this sequence of integrals is bounded.

EDIT: I have an attempted solution to this in a post below, it is very long, but still incomplete. EDIT:Alright, I've pretty much almost finished my solution, but my biggest problem is the 2nd ...
2
votes
1answer
506 views

2T(n/2) +n by induction

I try to proof by induction that: $$ T(n)= 2 T(n/2)+n \quad n>2,\quad T(2)=2,\quad n = 2^{k}$$ is $$ n*lg_2(n) $$ How can I do this? Thanks Steps that i went throw: ==Base Case== $$T(2) = 2, ...
0
votes
2answers
271 views

Strong mathematical induction: Prove Inequality for a provided recurrence relation $a_n$

The sequence $a_1,a_2,a_3,\dots$ is defined by: $a_1=1$, $a_2=1$, and $a_n=a_{n-1}+a_{n-2}-n+4$ for all integers $n\ge 3$. Prove using strong mathematical induction that $a_n\ge n$ for all integers ...
1
vote
2answers
85 views

Mathematical Induction Check, $n! \leq n^n/2^n $

Hello I am working on this problem and was wondering if I did the proof correct. Use induction to prove that $n! \leq n^n/2^n $ for all $n \geq 6$. Basic Step (n=6): 6! $\leq 6^6/2^3 = 3^6$ Thus $80 ...
2
votes
0answers
68 views

Proof for a finite number of elements

if I want to proof something for a restricted finite number of elements, meaning the following: Imagine that I have a theorem that is somehow similar to the following: For each element in ...
1
vote
2answers
136 views

Using mathematical induction to prove an identity related to combinatorics

Using Mathematical induction on $k$, prove that for any integer $k\geq 1$, $$(1-x)^{-k}=\sum_{n\geq 0}\binom{n+k-1}{k-1}x^n$$ How should I proceed? The tutorial teacher attempted this question and ...
3
votes
2answers
63 views

Soving Recurrence Relation

I have this relation $u_{n+1}=\frac{1}{3}u_{n} + 4$ and I need to express the general term $u_{n}$ in terms of $n$ and $u_{0}$. With partial sums I found this relation $u_{n}=\frac{1}{3^n}u_{0} + ...
4
votes
1answer
83 views

Confused on definition of strong induction

I found the following statement in Munkres' Topology: Theorem 4.2 (Strong induction principle). Let $A$ be a set of positive integers. Suppose that for each positive integer $n$, the statement ...
2
votes
3answers
92 views

Problem with Proof of Inequality with Squares by Induction

I am a bit new to logical induction, so I apologize if this question is a bit basic. I tried proving this by induction: $$\left(\sum_{k=1}^nk\right)^2\ge\sum_{k=1}^nk^2$$ Starting with the base ...
1
vote
2answers
53 views

determining the value of e by using mathematical induction

using the fact that $n!>2^{n}$ $\forall n\ge 4$ conclude that $e<\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\displaystyle\sum_{n=4}^{\infty}\frac{1}{2^{n}}$ where ...
4
votes
3answers
102 views

proving $n!>2^n\;\;\forall \;n≥4\;$ by mathematical induction

My teacher proved the following $n!>2^n\;\;\;\forall \;n≥4\;$ in the following way Basis step: $\;\;4!=24>16$ ok Induction hypothesis: $\;\;k!>2^k$ Induction step: ...
1
vote
3answers
85 views

Using induction to verify a statement

I have to prove that this statement is true. For $n = 1, 2, 3, ...,$ we have $ 1² + 2² + 3² + ... + n² = n(n + 1)(2n + 1)/6$ Basically I thought I'd use induction to prove this. Setting $n = p+1$, I ...
9
votes
2answers
163 views

Proving that $\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\dots+\frac{1}{\sqrt{100}}<20$

How do I prove that: $$\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\dots+\frac{1}{\sqrt{100}}<20$$ Do I use induction?
3
votes
1answer
143 views

what is ascending and descending induction?

On page 88 of Lang's "Topics in Cohomology of Groups", Lang mentions a technique he calls "ascending and descending induction". Initially I felt a bit embarrassed that I did not know a sort of ...
6
votes
5answers
96 views

Prove that $3^n>n^4$ if $n\geq8$

Proving that $3^n>n^4$ if $n\geq8$ I tried mathematical induction start from $n=8$ as the base case, but I'm stuck when I have to use the fact that the statement is true for $n=k$ to prove ...
2
votes
1answer
59 views

Prove that $n^2 \leq \frac{c^n+c^{-n}-2}{c+c^{-1}-2}$.

Let $c \not= 1$ be a real positive number, and let $n$ be a positive integer. Prove that $$n^2 \leq \frac{c^n+c^{-n}-2}{c+c^{-1}-2}.$$ My initial thought was to try and induct on $n$, but the ...
0
votes
2answers
78 views

How to prove this inequality by using induction?

If $x,y$ are distinct real numbers such that $x+y>0$ and $n\ge 1$, then $2^{n-1}(x^n+y^n)\ge (x+y)^n$. It is obvious for $n=1$. How to do the rest by using induction?
1
vote
1answer
58 views

Combinatorics identity sum of

Prove that: $$\sum^{n}_{k=0}\binom{k}{2n-k}2^k = 2^{2n}$$ By using only combinatorics identities.
2
votes
3answers
142 views

prove: $\dfrac{2^{n+1}+(-1)^n}{3}$

I am asked to prove this notation with induction for $n\in \mathbb{N}$: real problem is to fill the area with tilings. and for $n\in \mathbb{N}$ there are exactly so many chances to fill the area as ...
0
votes
0answers
91 views

Improper integral $\int_{0}^{\infty}\frac{x^n}{x^{m+n+1}} \ dx=\frac{n! {(m-1)}!}{(m+n)!}.$

How can I prove that $$\int_{0}^{\infty}\frac{x^n}{x^{m+n+1}} \ dx=\frac{n! {(m-1)}!}{(m+n)!}\quad ?$$ I tried to do induction on $n$ and on $m$, separately, but I could only do the base case ($n=1$ ...
2
votes
2answers
88 views

How to use induction to prove this argument?

It is obvious that this grammar will always return an equal number of both a's and b's. But I was wondering how to prove it using induction? I understand induction, but I was finding it hard to ...
2
votes
1answer
79 views

show by induction if there exists a $n_0 \in \mathbb N $such that $n\geq n_0 , n! \gt 2n^3$

I tried and I got there doesn't exist such a $n_0$ However, I dun think I have a formal proof for this. My approach is, First assume there is such a $n_o$ exist and start my calculation with ...
4
votes
3answers
360 views

Prove that $(a+1)(a+2)…(a+b)$ is divisible by $b!$ [duplicate]

The problem is following, prove that: $$(a+1)(a+2)...(a+b)\text{ is divisible by } b!\text{ for every positive integer a,b}$$ I've tried solving this problem using mathematical induction, but I ...
1
vote
2answers
541 views

proof by induction to demonstrate all even Fibonacci numbers have indices divisible by 3

I am practicing proof by induction, and would like to use induction to prove the following hypothesis about the Fibonacci numbers: $$(\forall n\ge0) \space 0\equiv n\space mod \space 3 \iff 0 \equiv ...
0
votes
1answer
140 views

Recursive Definitions with Converse

I think I know how to solve i. and ii., but not iii: Base Case: $(0,0) \in S$ Recursive Step: If $(a,b)\in S$, then $(a+1,b+2)\in S$ and $(a+2, b+1)\in S$. (For i and ii): Prove that if $(a,b) \in ...
2
votes
2answers
254 views

Another hat problem

A finite number of prisoners, after being given their hats (black or white), are able to see one another but themselves, and then they are ordered to jot down their guess on the color of their own ...
0
votes
2answers
75 views

Prove summation using induction [duplicate]

$$\sum\limits_{i=1}^n i^3 = \left(\frac{n(n + 1)}{2}\right)^2$$ My basis step is $P(1)$ sets the $LHS = RHS = 1$. For the inductive step, I assume $n = k$ holds for $k+1$. On the $RHS$: ...
0
votes
2answers
127 views

I need help with proofs using mathematical Induction

I need help with this problem: $2+7+12+17+...+(5n-3)=(\frac{n}{2})(5n-1)$
1
vote
1answer
85 views

Induction with compositions

Proposition. Suppose $g,h:\mathbb{R}\rightarrow\mathbb{R}, (g\circ h\circ g^{-1})^{n}=g\circ h^{n}\circ g^{-1}$ where $n\in\mathbb{N}$ and $g$ is a bijection. We will prove this by mathematical ...
12
votes
2answers
767 views

9 pirates have to divide 1000 coins…

A band of 9 pirates have just finished their latest conquest - looting, killing and sinking a ship. The loot amounts to 1000 gold coins. Arriving on a deserted island, they now have to split up the ...
3
votes
4answers
104 views

Induction proof: $\dbinom{2n}{n}=\dfrac{(2n)!}{n!n!}$ is an integer.

Prove using induction: $\dbinom{2n}{n}=\dfrac{(2n)!}{n!n!}$ is an integer. I tried but I can't do it.
2
votes
2answers
148 views

Induction on the Fibonacci sequence?

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. ...