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

3
votes
1answer
1k views

Induction Proof: Formula for Sum of n Fibonacci Numbers

I am stuck though on the way to prove this statement of fibonacci numbers by induction : my steps: definition: $F_{0}:=0, F_{1}:=1 $ and $F_{n}:=F_{n-1}+F_{n-2}$ The Hypothesis is: $\sum_{i=0}^{n} ...
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 ...
1
vote
1answer
224 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 ...
0
votes
2answers
203 views

Induction: Proving 2 Simple Weak Inequalities with Exponents of 2 and 3

I was wondering if you could help me with a trivial problem with inequalities that my teacher didn't really explain. Take for example: $3^n+2 ≤ 3^{n+1}$. How can I formally prove something as trivial ...
4
votes
1answer
149 views

Using Induction to Prove a Sequence is Strictly Increasing

Let $x_1=0 $ and for all n, $x_{n+1}$=$\sqrt{2+x_n}$ a)Prove: $x_n <2$ b)Prove: $x_{n+1} > x_n$ I made it through part a painlessly, however, b is giving me problems Part a: If $ x_k<2 ...
0
votes
3answers
186 views

If a statement is true for a particular n and for n+2, what needs to be done to prove the statement is true for every positive integer?

I am a bit confused with this question and any clarification or suggestions would be greatly appreciated. Suppose that there is a statement involving a positive integer parameter n and you have an ...
1
vote
2answers
269 views

Strong Induction: Prove provided recurrence relation $a_n$ is odd.

I'm not sure if we're allowed to post pictures but I thought it would be easier to read and I didn't see anything in the rules about it. It's question 1. Section 5.4 This question: Here is the ...
1
vote
3answers
409 views

Strong Induction: Every natural number $n\geq 8$ can be represented as $n=3k + 5\ell$

Can you please help me and tell, how should I move on? Can this be proved by induction? Every natural number $n\geq 8$ can be represented as $n=3k + 5\ell$. Thank you in advance
4
votes
1answer
519 views

What’s bogus about this Strong Induction Proof on weakly decreasing sequence of primes?

I couldn't find what is wrong with this strong induction proof, any one knows ? Question: A sequence of numbers is weakly decreasing when each number in the sequence is $\geq$ the numbers after it. ...
0
votes
3answers
225 views

Falsity about “Strong” Induction - Not Actually Stronger than Normal Induction?

I'm proving something via induction (which has turned into strong induction) and there's something I've never really fully understood about strong induction. The name "strong induction" does make it ...
0
votes
2answers
220 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 ...
3
votes
2answers
3k views

Strong Induction Proof: Every natural number = sum of distinct powers of 2

The question I'm looking at, is to show that every positive integer $n$ can be written as a sum of distinct powers of two. I can see that you can form any number based on the highest $2^t$ that is ...
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 ...
4
votes
2answers
3k views

Strong Induction: Example Using All of P(1) and … and P(k - 1) and P(k) to Prove P(k + 1)

I'm trying to understand how to do "real" strong induction, but my textbook seems to be of no help. It defines strong induction as follows: Let $P(n)$ be a property that is defined for integers ...
3
votes
2answers
83 views

Strong Mathematical Induction: Prove $3\mid b_n$ for a given recurrence relation $b_n$

Here is what I have so far: Proof $3\mid b_n$ for $n$ integers $\geq 1$ Base Cases both given $b_1=3, b_2=9$ and $b_n=6b_{n-2}+b_{n-1}$ $$P(1)=3\mid b_1$$ $$P(1)= 3\mid 3$$ Since $3\mid 3$, the ...
1
vote
2answers
459 views

Yet another confusion about Strong vs Weak Mathematical Induction - Wrong Proof?

In Mathematics literature, I am under the impression that there are at least two (non-trivially different) definition of Mathematical induction. I am assuming one is a weak form and the other is ...
2
votes
3answers
85 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
1answer
66 views

More Bases for Strong Induction - Supersedes Weak Induction?

I recently learned about strong induction, and had a couple questions. First, on sites such as this one: http://www.mathblog.dk/strong-induction/ , it is said that using strong induction requires more ...
2
votes
0answers
56 views

Writing down the induction principle formally

Can one write principle of mathematical induction formally in the following way ($ P $ and $ S $ are a predicate and the successor function, respectively)? $$(\exists x\in\mathbb {N}(P (x))\wedge ...
2
votes
1answer
222 views

Induction question: $P(n): 2 + 4 + … + 2n = (n + 2)(n - 1)$ for any integer $n \ge 2$.

I have to find an error in an induction exercise and I believe the error is in the basic step. Here is what I have, $P(n): 2 + 4 + ... + 2n = (n + 2)(n - 1)$ for any integer $n \ge 2$. My steps: ...
3
votes
4answers
72 views

using induction to prove $(n+1)^2 < 2n^2$

(Im not English and just started doing maths in English so my termiology is still way off) So the title for $n\ge 3$ First I use calculate both sides with $3$, which is true I make my induction. ...
0
votes
1answer
960 views

The cardinality of the power set with $N$ elements is equal to $2^N$ [duplicate]

Let $\mathcal{P}(X_N)$ be the power set of a set $X$ with $N$ elements. I am trying to prove by induction that its cardinality $\mid \mathcal{P}(X_N) \mid = 2^N$. Firstly, I think it helps to ...
1
vote
2answers
86 views

Induction proof $2n+1<2^n$ [duplicate]

I struggle to proof that: $2n+1<2^n$ By using induction. The base case is for $n\ge3$. Any help will be appreciated!
4
votes
4answers
191 views

Prove for all $m, n \in \mathbb N$: $[1 + 3 +\cdots + (2n -1)]^m = n^{2m}$

I have this: Prove for all $m, n \in \mathbb N$: $$[1 + 3 + \cdots + (2n - 1)]^m = n^{2m}$$ For $n = 1: 1 = 1^2$, hence P(1) is true. Let $N \in \mathbb N$ be given and assume: $$[1 + 3 + \cdots ...
4
votes
4answers
53 views

Prove that $1^3 + 2^3 + 3^3 +\cdots+ n^3 = \frac14n^4 + \frac12n^3 + \frac14n^2$

I have to prove that this is true using mathematical induction. I have this: for every $n \in \mathbb N$: $1^3 + 2^3 + 3^3 + ... + n^3 = \frac 14n^4 + \frac 12n^3 + \frac 14n^2$ for $n = 1: 1^3 = ...
2
votes
1answer
71 views

if its true for $n$ is it true for $n-1$ (mathematical induction)?

the induction rule , if we suppose that $p(n)$ is true , is $p(n-1)$ true as well? if $1+2+...+n=\frac{n(n+1)}{2}$ is it true than $1+2+...+n-1=n-1(n-1)/2$ (before proving the statement for $p(n+1)$ ...
-1
votes
1answer
87 views

Simple Question about Induction?

let x be a natural number i want to prove that f(x)=$x^2$. suppose that f(x)=$x^2$, f(0)=0 holds we'll prove that f(x)= $(x+1)^2$, in the functional equation we have f(x-y)+f(x+y)=2f(x)+ stuff, ...
0
votes
1answer
505 views

Induction proof for the lengths of well-formed formulas (wffs)

Use induction to show that there are no wffs of length 2, 3, or 6, but that any other positive length is possible. The wffs in question are those associated with sentential/propositional logic. So, ...
0
votes
4answers
109 views

Math analysis $n^2>n+1$ [closed]

So by induction $n^2<n+1$ is $Pn$ and holds for all integers n less than and equal to 2 For $P_n+1$ $(n+1)+1<(n+1)^2 \\ <n^2+2n+1 \\<(n+1)^2+2(n+1)+1$ Is the the correct way to ...
2
votes
1answer
42 views

Babble Strings and Induction

I normally don't have any problems doing proofs by induction. However, in this case I'm struck because I have difficulty seeing how exactly I should approach the problem and construct the proof. Would ...
4
votes
5answers
911 views

Proving sum of $1/n^2$ is less than or equal to $2$ [duplicate]

So I'm suppose to prove that $\sum 1/n^2 \le 2$. Should I use induction?
6
votes
2answers
275 views

Prove that the sequence given by $c_n = \sqrt{1+c_{n-1}}$ converges and find the limit

Let $c_1 = 2$, and for $n > 1$, let $c_n = \sqrt{1+c_{n-1}}$. Prove: (by induction) that $c_n < 2$, for $n > 1$. (by induction) that {$c_n$} is monotonically decreasing. that ...
1
vote
1answer
154 views

Strong Induction proof

Suppose that $x$ subset of Real numbers such that $x + \frac{1}{x}$ is subset of Rational numbers. Using strong induction, show that for each $n$ subset of Natural numbers, $A_n = x^n + \frac{1}{x^n}$ ...
5
votes
5answers
208 views

Prove $n!>n^2$ for $n>3$

I'm aware that induction is necessary. I have been stuck on this problem for a few days now. I'm having a hard time understanding how to apply the inductive hypothesis to the inequality to arrive at ...
4
votes
5answers
370 views

Prove that $1^3 + 2^3 + \cdots + n^3 < n^4$.

I am trying to prove the following: $1^3 + 2^3 + \cdots + n^3 < n^4$ if $n \in \mathbb{N}, n>1$ by induction. From there, I am to prove that the sum is $< \frac{n^4}{2}$ if $n>2$. My ...
3
votes
2answers
140 views

Prove that $2^n>2n$ for all integral values of n greater than 2 [duplicate]

Prove $2^n >2n$ for all integral values of n greater than 2. Let $p_n$ be the statement: $$2^n>2n\ \forall\ n\gt2$$ If the inequality is valid for $n=k$ where $k>2$: $$p_k: 2^k>2k$$ ...
1
vote
3answers
397 views

Showing Whether a Sequence is Bounded Above or Not

I am trying to solve the following problem about a sequence: Consider the sequence ${a_n}$ where $a_n = 1 + \frac{1}{1 \cdot 3} + \frac {1}{1 \cdot 3 \cdot 5} + \frac {1}{1 \cdot 3 \cdot 5 \cdot 7} + ...
3
votes
7answers
854 views

Prove $n^2 > (n+1)$ for all integers $n \geq 2$

I understand that I need to use induction for this, that's not a problem. I get stuck after I try to invoke the inductive hypothesis. $P_n: n^2 > n+1$... and we want to prove $P_{n+1}: (n+1)^2 ...
1
vote
1answer
301 views

Induction on a well-formed formula (wff)

Let α be a well-formed formula (wff); let c be the number of places at which binary connective symbols (∧, ∨, →, ↔) occur in α; let s be the number of places at which sentence symbols occur in α. (For ...
0
votes
1answer
86 views

Recursive fibonacci algorithm correctnes? [proof by induction]

im studying for the computer science GRE, as an exercise i need to provide a recursive fibonacci algorithm and show its correctness by mathematical induction. here is my recursive version of ...
1
vote
1answer
91 views

Critique on a proof by induction that $\sum_{i=1}^n i^2= n(n+1)(2n+1)/6$?

I need to make the proof for this 1:$$1^2 + 2^2 + 3^2 + ... + n^2=\frac{(n(n+1)(2n+1))}{6}$$ By mathematical induction I know that, If P(n) is true for $n>3^2$ then P(k) is also true for k=N and ...
3
votes
2answers
111 views

Help with a proof by induction.

I'm reading On Mathematical Induction by Leon Henkin in JSOTR. And well, in the first part of the article the author given us the necessary properties to be a Peano Model. A model $\langle ...
0
votes
2answers
158 views

Strong Induction on Inequalities

I'm asked to indicate which natural numbers $n$ each of the below inequality is true, and then I am required to prove this via induction, but I'm wondering what that means... Strong induction? ...
-1
votes
1answer
83 views

Revisited: Binomial Theorem: An Inductive Proof

I'm asked to use the fact that $\begin{pmatrix}n\\r\end{pmatrix}+\begin{pmatrix}n\\r-1\end{pmatrix}=\begin{pmatrix}n+1\\r\end{pmatrix}$ to show, by induction, that ...
1
vote
1answer
79 views

¿Mathematical induction GRE math?

Im studing for the GRE math subject test...i can´t get the followin problem: Using Mathematical Induction, show that it is possible to color with only two colors the regions formed by n lines in the ...
3
votes
1answer
110 views

A formula for n-derivative of the inverse of a function?

Let $y=f^{-1}(x)$. As we know: \begin{align} \frac{\mathrm{d} y}{\mathrm{d} x}=\frac{1}{{f}'(y)} \end{align} Thereof we have: \begin{align} \frac{\mathrm{d^2} y}{\mathrm{d} ...
2
votes
2answers
46 views

Not understanding part of inductive proof

$n!\gt 2^{n}$ for $n \geq 4$. Then there is an inductive proof: We assume that $n! \gt 2^{n}$ for every random $n \in \mathbb{N}$ with $n\geq4$, and we need to proof that $(n+1)!\gt 2^{n+1}$. ...
0
votes
1answer
65 views

How do i prove there exists a function $F(n+1)=f_n(F(1),…,F(n))$?

Let $X$ be a set and $f_n:X^n \rightarrow X$ be a function for all $n\in \mathbb{N}$ and $c\in X$. How do i prove that there exists $F:\mathbb{N} \rightarrow X$ such that $F(n+1)=f_n(F(1),...,F(n))$ ...
2
votes
2answers
51 views

Interpretation in notation for making a proof and substitution processes

It is asked to be prove: $$\forall{n}\in{N}:(n+1)(n+2)(n+3)...(n+n)=2^n\cdot1\cdot3\cdot5...\cdot(2n-1)$$ 1 Step p(n) is assumed to be true for n=1 ...
1
vote
1answer
52 views

Mathematical induction last step…

Proof: $$\forall{n}\in{N}:1(1!)+2(2!)+3(3!)+...+n(n!)=(n+1)!-1$$ Step 1 Prove p(n)=>True for n=1 $$1(1!)=(1+1)!-1$$ $$1=1$$ Step 2 Assume by induction that (k)=>true ...