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

learn more… | top users | synonyms

0
votes
1answer
108 views

Round Robin Tournament

For any non-negative integer, $n$, suppose there are $2^n$ teams in a round robin tournament, and every team plays against each other team exactly once. Prove that we can find $n+1$ teams who can be ...
1
vote
1answer
34 views

Use induction to prove that $a^n + b^n \leq (a+b)^n$

I am doing some exercises in proving things and I am stuck on this proof: $a^n + b^n \leq (a+b)^n$, $a,b > 0$, for every $n > 0$. I start with $n = 1$: $a^1 + b^1 \leq (a+b)^1$. Then I ...
0
votes
1answer
32 views

Algebraic Manipulation for Mathematical Induction

I'm working on a mathematical induction problem. The question is as follows: $P = \begin{pmatrix} 1-A & A \\ B & 1-B \\ \end{pmatrix}$ for A,B $\epsilon$ (0, 1). Show by induction, or ...
0
votes
0answers
42 views

Tricky notation: Need help formulating an expression to define a recursive function involving substitutions

I'm having a difficult time trying to come up with an inductive definition for a function I'm calling $f_i(k)$ in terms of constants $\rho$, $d$, the $1 \times n$ vector $q$, and a $n \times n$ matrix ...
0
votes
2answers
73 views

How to prove this inductive form?

Assuming $\exists n \ge 2: P_n$, $\;\neg P_k \implies \neg P_{k-1}$, and $\neg P_1$, is it valid to conclude $\exists! k , 1 < k \le n: P_k \wedge \neg P_{k-1}$? What theorem or technique would I ...
13
votes
6answers
1k views

Principle of Transfinite Induction

I am well familiar with the principle of mathematical induction. But while reading a paper by Roggenkamp, I encountered the Principle of Transfinite Induction (PTI). I do not know the theory of ...
3
votes
1answer
41 views

Demonstrate $f(a,b)=2^a (2b+1)-1$ is surjective using induction

I am trying to show that $f:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$, where $f(a,b)=2^a (2b+1)-1$, is surjective using induction (possibly strong induction). In the case $n=0$, it is easy to ...
3
votes
1answer
1k views

Prove that square root of 2 is irrational using the principle of Mathematical Induction

How do I prove that the square root of 2 is irrational using the principle of mathematical induction?
0
votes
0answers
8 views

Using Euclid's algorithm and applying it to pair $(u,v)$ takes $n$ steps. Prove then that $u \geq f_{n+2}$ and $v \geq f_{n+1}$. [duplicate]

Prove that if Euclid's algorithm applied to the pair $(u,v)$ takes $n$ steps, then $u \geq f_{n+2}$ and $v \geq f_{n+1}$. Where the $f$ is used to represent the Fibonacci numbers, and we know that it ...
2
votes
1answer
33 views

Extension of induction principle proof.

i was wandering if is there an extension of the induction principle whether number the integer variables are more than 1? Example... if i need to prove that $p(n)$ is true then i would start by prove ...
3
votes
3answers
98 views

Prove using induction

I have this math problem I'm kind of stuck on. Here's the question: Define a sequences of real number with the definitions $$\begin{align*} x_1 & = 3 \\ x_n &= \sqrt{2 x_{n-1}+1} \text{...
0
votes
2answers
34 views

Proving an identity of Fibonacci Numbers by induction

Say we know this as a given: $$E_0 = A$$ $$E_1 = B$$ $$E_2 = A + B$$ $$E_3 = A + 2B$$ $$E_4 = 2A + 3B$$ $$E_5 = 3A + 5B$$ $E_{n+1}$ is defined as: $$E_{n+1} = E_n + E_{n-1}$$ You can start to see ...
0
votes
2answers
23 views

Having trouble understanding the steps of this half angle identity

How does the solution go from $\sqrt{2\left(1+\cos\left(\frac{\pi}{2^{n+1}}\right)\right)}$ to $4\cos^2(\ldots)$? Where does the $4$ come from? I understand that the identity is $\cos^2(2x) = \cos(1+\...
11
votes
4answers
3k views

Examples of transfinite induction

I know what transfinite induction is, but not sure how it is used to prove something. Can anyone show how transfinite induction is used to prove something? A simple case is OK.
8
votes
4answers
235 views

How to “make up a formula” of a sum: $S=2+7+12+\cdots+(5n-3)$?

I was asked the following: Determine a formula for the following sum with $n\in\mathbb N$: $$S=2+7+12+\cdots+(5n-3)$$ I had no clue about what to do about it. I just wrote, for the sake of doing ...
2
votes
2answers
51 views

Using induction to prove a formula for the Fibonacci sequence involving the solutions of $x^2=x+1$

Let $\{f(n)\}_{n=1}^{\infty}$ denote the Fibonacci sequence defined by $f(1)=1, f(2)=1$, and $f(n)=f(n-1)+ f(n-2)$ for all $n\geq 3$. Let $α=\dfrac{1+\sqrt{5}}{2}$ and $β=\dfrac{1-\sqrt{5}}{2}.$ ...
2
votes
2answers
690 views

Proving arithmetic series by induction

How do I prove this statement by the method of induction: $$ \sum_{r=1}^n [d + (r - 1)d] = \frac{n}{2}[2a + (n - 1)d] $$ I know that $d + (r - 1)d$ stands for $u_n$ in an arithmetic series, and the ...
1
vote
1answer
42 views

Prove using induction / Strong induction

I have a problem: Let $a_0=0, a_1=1$, and let $a_{n+2}=6a_{n+1}-9a_n$ for $n\geq 0$. Prove that $a_n=n\cdot 3^{n-1}$ for all $n\geq 0$. And I am assuming that this can be solved via induction. ...
0
votes
2answers
46 views

Strange induction proof

I'm trying to solve an induction proof exercise but this time I can't even understand how to proceed. I must prove that for every given $n\in \mathbb{N}$ with $n\geq2$ there exist $a,a_1,a_2,...,a_n$ ...
0
votes
3answers
43 views

Prove by induction this sequence

Prove by induction, that $$a_n=\frac{n+1}{n-1}(a_1+a_2+\ldots+a_{n-1})$$ is $$a_n=(n+1)2^{n-2}\;,$$ where $a_1=1$. I have tried the indution step, but cannot succeed.
0
votes
1answer
72 views

Mathematical induction proof of $\sum_{i = 1}^{n} F_{2i} = F_{2n + 1} - 1$

Use Mathematical Induction to show that $$\sum\limits_{i=1}^n F_{2i}=F_{2n+1}-1$$ for all integer $n\geq1$. My answer: Base case: for n = 1 $$\sum_{i = 1}^{n} F_{2i} = \sum_{i = 1}^{1} F_{2i} = ...
0
votes
1answer
42 views

Proving Fibonacci sequence with mathematical induction

Okay, so I have the following thing: $$\sum_{i=1}^a F_{2i}=F_{2a+1}-1 $$ It's to do with Fibonacci sequence. I can do the basis step of MI fine (proving for $a = 1$) However the inductive step has ...
0
votes
0answers
15 views

Use structural induction that P is true for all $e \in P$.

Let E be the smallest set such that: $x,y,z∈E$ If $e_{1}$ and $e_{2}$ are in E, then the following four elements are in E: $(e_1 +e_2), (e_1 −e_2), (e_1 ×e_2), (e_1 ÷e_2)$ Three base elements, ...
-1
votes
6answers
95 views

Prove by induction that $n^3-n+3$ is divisible by 3 for all natural numbers $n$ [closed]

Show that $n^3-n+3$ is divisible by $3$ for all natural numbers $n$ What would the step by step induction proof be?
0
votes
3answers
190 views

Prove that the Union of [1/n,n] = (0,∞) from n=1 to ∞

So I'm having trouble starting the proof mainly because I don't know which proof technique to use. I thought about using the Principle of Mathematical Induction but it doesn't seem like the correct ...
0
votes
3answers
85 views

Proof on Fibonacci sequence: $F(1) + F(3) + \cdots + F(2n-1) = F(2n)$ using induction and recursion

The problem is: Use induction and the recursive formula to prove that: $$F(1) + F(3) + \cdots + F(2n-1) = F(2n)$$ For the base case I let $n=1$ which gave $$F(1) = F(2(1))$$ $$1=1$$ Which is ...
1
vote
1answer
44 views

Strengthening an inequality

I'm reading a book and there's an example problem that goes like this: Prove that $$ \left(\frac{1}{2}\right) \left(\frac{3}{4}\right) ... \left(\frac{2n-1}{2n}\right) \le \left(\frac{1}{\sqrt {3n}}\...
0
votes
2answers
107 views

How do I prove this using mathematical induction? [duplicate]

$\sum_{k = 1}^{n}k\binom{n}{k}=n2^{n-1}$ How do I prove this using mathematical induction?
0
votes
1answer
26 views

How can I develop this using induction?

I'm trying to prove using induction that $a^n +b^n = (a-b) \cdot \sum\limits_{k=1}^{n}a^{n-k}b^k-1$ So I have developed the expression for $n+1$ but I get to $a \cdot b^n - b^{n+1} + a^n - b^n$ And ...
1
vote
1answer
41 views

Proof by induction, induction step

I am trying to prove $$ \sum_{k=1}^n k2^{k-1} = 1+(n-1)2^n $$ I proved the base case with $n = 1$. I am having trouble proving the induction step. I know I need to prove for $n = n +1$ so I got $...
0
votes
4answers
303 views

Prove the laws of exponents by induction

We inductively define $a^1=a, a^{n+1}=a^n a$. I want to show that $a^{n+m}=a^n a^m$. By definition, this is true if $m=1$. Now for $m=2$, we have $$ \begin{align} a^{n+2} =& a^{(n+1)+1}\\ =&...
1
vote
2answers
52 views

Prove $n^2 \leq 1.1 ^{n}$ by induction

Prove that for all $n \geq 100$ you have $n^2 \leq 1.1^n$ Base Case: $n = 100$ $(100)^2 \leq 1.1^{100}$ (True) Inductive Case: Suppose $(k-1)^2 \leq 1.1^{k-1}$ for some $k \geq 101$ Prove $k^...
3
votes
2answers
59 views

Mathematical induction and Stirling numbers

I want to find a formula for the following series $$ \sum_{i=1}^m {m \choose i} i! S(n,i)$$ Where $S(n,m)$ is the Stirling numbers of the second kind. Now I evaluated this series at $m=1,2,3$ for ...
0
votes
4answers
58 views

Prove by Induction help?

Prove by induction that for $1 \le n$: $$\sum_{k=1}^n k(k + 1)(k + 2) = 6 + 24 + . . . + n(n + 1)(n + 2) = \frac 14 n(n + 1)(n + 2)(n + 3) $$ Basis step: I got $n(1) = 6$ and ...
0
votes
2answers
60 views

Proving $a^n-b^n=(a-b)\sum_{k=1}^{n}a^{n-k} b^{k-1}$ with induction [duplicate]

How can I prove this using induction. I proved for n=1 but now I'm feeling confused while I'm trying to prove for n+1 because of how the summation develops $$ a^n-b^n=(a-b)\sum_{k=1}^{n}a^{n-k} b^{k-...
0
votes
0answers
28 views

Extended Transition Function Equivalent Proof

I encounter a difficult question (for me), and until now I haven't found a solution for it. In this question, I have to proof that these two are equivalent using induction. ...
2
votes
2answers
79 views

Mathematical induction and pigeon-hole principle

I am trying to prove that if $n$ is even and if $n+1$ integers are chosen from the set $\{1,2,....,2n \}$ then there are always two integers that differ by 2. In my attempt. I try $n=2$, and so ...
0
votes
0answers
81 views

Waiting times independence and distribution

I am struggling with that: We have irreducible and aperodic Markov Chain on finite state space. There is a state $\alpha$ which is recurrent. We define $\tau_n = \min (m >{\tau_{n-1} : X_m = \...
3
votes
3answers
65 views

Prove that $5^{2n-1} - 3^{2n-1} - 2^{2n-1}$ is divisible by 15 for n $\in$ $\mathbb{N}$

The book I am using for my Combinatorics course is Combinatorics:Topics, Techniques, and Algorithms. Prove that $5^{2n-1} - 3^{2n-1} - 2^{2n-1}$ is divisible by 15 for n $\in$ $\mathbb{N}$ This is ...
0
votes
1answer
40 views

Proving a Recursive Definition using Induction

I have the following recursive definition of a set $S \subseteq \mathbb N \times \mathbb N$ : ...
2
votes
5answers
61 views

Prove $5 \mid (3^{4n} - 1)$ by induction

I need to prove by induction that $5 \mid 3^{4n} - 1$ for $n \ge 1$. Base case is true, so now I have to prove that $5 \mid 3^{4(n+1)} - 1$. I did $$= 3^{4n+4} -1$$ $$= 3^{4n} 3^{4}-1$$ I guess I ...
1
vote
2answers
44 views

Please explain this basic proof

In my freshman math course book there's a proof of associativity of addition on the natural numbers using mathematical induction. The author proves the base case and assumes the hypothesis, $a+(b+c) = ...
2
votes
3answers
316 views

Proving $\prod((k^2-1)/k^2)=(n+1)/(2n)$ by induction

$$P_n = \prod^n_{k=2} \left(\frac{k^2 - 1}{k^2}\right)$$ Someone already helped me see that $$P_n = \frac{1}{2}.\frac{n + 1}{n} $$ Now I have to prove, by induction, that the formula for $P_n$ is ...
1
vote
0answers
28 views

Prove by induction that this sum is not a natural number. [duplicate]

Prove by induction that $1+\frac{1}{2}+\frac{1}{3} +...+\frac{1}{n}$ for any $1<n$ and $n\in \Bbb{N}$ is not a natural number.
2
votes
2answers
67 views

Proofs: Induction on Handshakes

Here is the problem: Suppose $n$ people are at a party, and some number of them shake hands. At the end of the party, each guest $G_i$, $1 \leq i \leq n$ shares that they shook hands $x_i$ times. ...
2
votes
2answers
73 views

Can you use proof by contradiction inside simple induction?

During a proof using simple induction, I assumed P(k) is true. Now in order to show P(k+1) is true using P(k), can I do a proof by contradiction on P(k+1) and say P(k) would be wrong if P(k+1) is ...
0
votes
3answers
83 views

Proving $\sum_{i=1}^ni(i+1)=n(n+1)(n+2)/3$ for $n\geq 1$ by induction

I'm trying to prove this by induction: $$1*2 + 2*3 + 3*4 + \cdots + n(n+1) = (n(n+1)(n+2))/3.$$ I have done this so far: Base Case: $n = 1$, works for both. Induction Hypothesis: Let $n = k$, ...
1
vote
0answers
76 views

Proof of the well ordering principle without mathematical induction

Is it possible to prove the well ordering principle without using mathematical induction? If yes, how?
1
vote
2answers
53 views

Proving $n! > n^2$ by mathematical induction [duplicate]

I'm trying to prove that $n! > n^2$ for $n\geq 4$ by use of mathematical induction, but I get to the inductive step and get lost. But I'm struggling with the inductive step as expected.