For questions about mathematical induction, a method of mathematical proof. Mathematical induction generally proceeds by proving a statement for some integer, called the *base case*, and then proving that if it holds for one integer then it holds for the next integer. This tag is primarily aimed ...

learn more… | top users | synonyms

-1
votes
2answers
2k views

solve recurrence relation using mathematical induction?

solve recurrence relation $a_n = 6 a_{n–1} – 9 a_{n–2}$, where $a_0 = 1$ and $a_1 = 6$ and Verify, using Principle of Mathematical Induction, that $a_n = 3^n + n 3^n$. ans: i have done so far... put ...
0
votes
2answers
526 views

Induction step for $\sum\limits_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$

I want to prove by induction that, $\sum\limits_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$ OK I got the initial step, however, I have problems with the induction step: Here is what I tried: ...
1
vote
1answer
119 views

induction (sum of squares of products of elements of certain subsets of $\{1,\dots,n\}$)

Let $n$ be any natural number. Consider all nonempty subsets of the set {$1,2,...,n$}, which do not contain any neighboring elements. Prove that the sum of the squares of the products of all numbers ...
2
votes
1answer
106 views

Using Mathematical Induction for a proof

How can I use Mathematical Induction to prove that there are an infinite number of prime numbers?
2
votes
1answer
463 views

Proof Involving Connected Components of a Graph

I have the following problem: prove that every graph with $n$ vertices and $n-k$ edges has at least $k$ connected components. I have approached this proof using induction, but am having difficulty ...
1
vote
1answer
96 views

Proof through induction that all formulas with a certain characteristic are a tautology or logical equivalence of p

First, sorry for the long title but I couldn't figure out how to summarize it better. This is a homework question for my course "Introduction to Logic" and I can't figure out how to solve it. The ...
4
votes
4answers
200 views

Prove $3^n \ge n^3$ by induction

Yep, prove $3^n \ge n^3$, $n \in \mathbb{N}$. I can do this myself, but can't figure out any kind of "beautiful" way to do it. The way I do it is: Assume $3^n \ge n^3$ Now, $(n+1)^3 = n^3 + ...
4
votes
2answers
384 views

Prove the principle of mathematical induction in $\sf ZFC $

How does one prove the principle of mathematical induction using the standard axioms of $\sf ZFC $?
2
votes
1answer
40 views

Prove that there exist a pal number with n digits n>1.

We call a number pal if it doesn't have a non zero digit and the sum of the squares of the digits is a perfect square.For example 122 and 34 are pal but 302 and 12 are not pal.Prove that there exist a ...
1
vote
1answer
649 views

Well ordering principle vs induction proof

I was asked to recast an induction proof to a proof by well ordering princple. How are the 2 different? From my understanding the two are equivalent, so how will the proof be different? Thanks!
3
votes
2answers
139 views

Prove that if $a_{n+1} = a_n^2$, the last $n$ digits of $a_{n+1}$ are the same as the last $n$ digits of $a_n$.

I have been working on this problem for a while. I know that I have to prove it using induction, but I'm unsure of the next step. The formula for the terms is: $a_{n+1} = 5^{2n}$ with $a_1 = 5$. The ...
-2
votes
1answer
237 views

Induction Proof - Computation Theory [closed]

For my theory of computation class, we are supposed to do some review/practice problems to work off the rust and make sure we are ready for the course. Some of the problems are induction proofs. I did ...
0
votes
2answers
299 views

Big-O Induction

In my Algorithms course, our first assignment is a set of induction problems. I learned (very poorly) how to do this in my discrete mathematics course two years ago, but it wasn't a very comprehensive ...
2
votes
2answers
528 views

Induction and Recursion: $f(1)=2$ and $f(n)=f(n-1)+2n$ for $n>1$

I have bad time with induction and recursion and I have an exam soon. We have this: $$f(1)=2$$ $$∀n>1:f(n)=f(n-1)+2n$$ We need to proof that is the solution of f(n)=f(n-1)+2n,f(1)=2 is: (the ...
1
vote
1answer
96 views

The sum of odd powered real numbers equals zero implies the numbers are inverses

Show that if real numbers $a_1,a_2,\ldots,a_n$ satisfy $$a_1^l+a_2^l+\cdots+a_n^l=0$$ for every odd $l$, then for any $a_i$ we can always find some $a_j$ (not necessarily different) such that ...
5
votes
3answers
2k views

Strong Induction Proof: Fibonacci number even if and only if 3 divides index

The Fibonacci sequence is defined recursively by $F_1 = 1, F_2 = 1, \; \& \; F_n = F_{n−1} + F_{n−2} \; \text{ for } n ≥ 3.$ Prove that $2 \mid F_n \iff 3 \mid n.$ Proof by Strong Induction : ...
5
votes
0answers
149 views

Cauchy induction: are there examples of cases where choosing an integer other than $2$ is a better strategy?

Cauchy induction, sometimes called backwards induction, works as follows: show that $p(1)$ is true show that $p(n)$ implies $p(2n)$ (which inductively implies $p(2^n)$ is true) show that $p(n)$ ...
2
votes
0answers
57 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 ...
7
votes
1answer
761 views

Proof by induction on Fibonacci numbers: show that $f_n\mid f_{2n}$

I was studying Mathematical Induction when I came across the following problem: The Fibonacci numbers are the sequence of numbers defined by the linear recurrence equation- $f_n = f_{n-1} + ...
3
votes
4answers
77 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. ...
2
votes
1answer
230 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: ...
0
votes
1answer
2k 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
1answer
303 views

Graph Theory: Graph with bipartite subgraph has MORE than e(G)/2 edges.

Show that every loopless graph G has a bipartite subgraph with more than e(G)/2 edges. Use induction on the number of vertices. Clearly if n(G) = 2, the hypothesis holds. But I am not sure how to ...
3
votes
3answers
110 views

Representation of all numbers that bigger than $12$ by $3x+7y$ proof

I found an exercise in my book that requested from me to proof that all numbers that bigger than $12$ can be represented by: $3x+7y$ They requested an induction proof,and i decided to share my ...
1
vote
2answers
95 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!
-2
votes
1answer
910 views

A question on proving the sequence is bounded above by 2 [closed]

I'm still struggling to fully understand induction. Could someone help me find a way to prove, using induction, that the sequence $$x_1=1$$ $$x_{n+1}=\frac{1}{2x_n} + 1$$ is bounded above by 2; that ...
4
votes
1answer
2k views

Exclusion Inclusion Principle Induction Proof

I got new home work that I was asked to proof the exclusion inclusion principle with induction, and my question is how can I do that? Any help will be appreciated!
4
votes
4answers
214 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
57 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
90 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, ...
1
vote
1answer
785 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
115 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
55 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 ...
0
votes
3answers
201 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 ...
5
votes
2answers
1k views

Inductive proof of the closed formula for the Fibonacci sequence [duplicate]

Fibonacci numbers $f(n)$ are defined recursively: $f(n) = f(n-1) +f(n-2)$ for $n > 2$ and $f(1) = 1$, $f(2) = 1$. They also admit a simple closed form: $$\sqrt 5 f( n ) = \left(\dfrac{1+ \sqrt ...
4
votes
5answers
1k 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?
1
vote
1answer
86 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 ...
6
votes
2answers
306 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
176 views

If $x$ is real and $x + \frac1x$ is rational, show by strong induction that $x^n + \frac{1}{x^n}$ is rational for all $n$.

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
212 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
381 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 ...
4
votes
2answers
209 views

Fibonacci using proof by induction: $\sum_{i=1}^{n-2}F_i=F_n-2$

everyone. I have been assigned an induction problem which requires me to use induction with the Fibonacci sequence. The summation states: $$\sum_{i=1}^{n-2}F_i=F_n-2\;,$$ with $F_0=F_1=1$. I ...
3
votes
2answers
198 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
678 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
1k 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 ...
2
votes
1answer
544 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
95 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 ...
0
votes
4answers
104 views

Mathematical Induction problem

Can somebody help me with these questions? I can't seem to get started... Having P (n) : n2 + 5n + 1 is even. a) Demonstrate that if P(k) is True to some k natural, then P(k + 1) is also true. b) ...
3
votes
2answers
125 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 ...