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
2answers
34 views

Proof By Induction for function

I am an undergrad Computer Engineering Student that is struggling through a class in discrete mathematics. One question in particular from a recent assignment has me stumped. Assuming that $T$ is a ...
0
votes
1answer
48 views

Induction, set theory drama

Let $P$ be a subset of $\def\N{\mathbf N}\N$ so that for all $n \in \N$, if forall $m \in \N$ with $m<n$ we have $m\in P$, then $n \in P$. Then $P=\N$ (prove this with induction) Now what if I ...
-1
votes
4answers
609 views

Mathematical Induction Proof: $1/\sqrt1 + 1/\sqrt2+…+1\sqrt n \ge \sqrt n$ [closed]

I need the full proof/solution to this problem. What I've done so far:
0
votes
2answers
38 views

Show $\frac{3\cdot 7\cdot 11\cdot _{…}\cdot\left(4n-1\right)}{5\cdot9\cdot13\cdot _{…}\cdot \left(4n+1\right)\:}<\sqrt{\frac{3}{4n+3}}$ for $n>0$

I need to prove that the expression: $$\frac{3\cdot 7\cdot 11\cdot _{...}\cdot \left(4n-1\right)}{5\cdot 9\cdot 13\cdot _{...}\cdot \left(4n+1\right)\:}<\sqrt{\frac{3}{4n+3}}$$ holds true for all ...
1
vote
2answers
61 views

Proving $1\cdot1! + 2\cdot2! + 3\cdot3! + … + k\cdot k! = (k+1)! - 1$ [duplicate]

How could one prove by induction that: $$\forall{n}\in{N}:1(1!)+2(2!)+3(3!)+...+n(n!)=(n+1)!-1$$ My attempt so far: Base case: Let n = 1, 1(1!) = (2)! - 1 = 1, holds true for LHS = RHS. Inductive ...
1
vote
1answer
28 views

Proof a Sum with real numbers

I have to prove with Induction that: $ \sum_{i=1}^n a^{i-1} = \frac{a^n -1 }{a-1}$ where $a \in R $ \ {0,1} with $a^0$ = 1 In the first induction step I get to divide by 0, because for a=1 it's 1-1. ...
1
vote
1answer
42 views

module of sum is less than…

Somehow need to prove: $$|x_1 + x_2 + ... + x_n| \le \sqrt{n(x_1^2 + x_2 ^ 2 + ... +x_n^2)}$$ $x_i$ is a real number; $i = 1,...,n$ Here's mentioned that mathematical induction should help. ...
0
votes
2answers
120 views

What is wrong with the proof [duplicate]

What is wrong with the following “proof” by Mathematical Induction? We will prove statements that all computers are built by the same manufacturer. In particular, we prove statements B(n) with n ∈ N, ...
1
vote
1answer
21 views

Induction T/F questions. How to know what the counterexample is.

Determine whether the statement is true of false. If true, provide a proof. If false provide a counterexample. for $n \in N, 2n-8 < n^2-8n+17$ I started off like a typical induction proof. ...
0
votes
1answer
103 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
41 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 ...
3
votes
1answer
40 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 ...
-2
votes
3answers
141 views

Induction Proof and Trigonometric Identities [closed]

Use trigonometric identities and induction to prove that $\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{n} = \left(\begin{array}{cc} ...
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 ...
0
votes
2answers
33 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) = ...
3
votes
3answers
92 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} ...
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. ...
2
votes
2answers
50 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}.$ ...
0
votes
2answers
44 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
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
1answer
70 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
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
170 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 ...
1
vote
2answers
111 views

Real analysis problem: Rolle's theorem, Darboux's theorem, induction

I am taking a course in real analysis (undergraduate) and I'm supposed to solve a problem and present in class. I've just started, but I'm already stuck. This is the problem: Let a function $f$ be ...
0
votes
3answers
83 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
42 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 ...
0
votes
2answers
106 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?
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 ...
1
vote
2answers
51 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 ...
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 ...
3
votes
2answers
57 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
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. ...
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 ...
1
vote
1answer
42 views

Absolute value of product is less than product of absolute values: $|(1+a_1)(1+a_2)\dots (1+a_n)-1|\leq (1+|a_1|)(1+|a_2|)\dots (1+|a_n|)-1$

For a sequence $a_n\in\mathbb{C}$ I want to show that $$|(1+a_1)(1+a_2)\dots (1+a_n)-1|\leq (1+|a_1|)(1+|a_2|)\dots (1+|a_n|)-1$$ I think I should show this by induction on $n$. For the base case I'm ...
2
votes
2answers
78 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 ...
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
39 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) = ...
0
votes
2answers
33 views

Proving $\prod_{i=2}^{i=n} \left(1-\frac{1}{i^2}\right) = \frac{n+1}{2n}$ by induction

So I have to prove the following using induction. ${\displaystyle \prod_{i=2}^{i=n} \left(1-\frac{1}{i^2}\right)} = \frac{n+1}{2n}$ I showed the basis step that if $n=i=2$, then the two functions ...
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.
1
vote
0answers
75 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?
2
votes
1answer
63 views

Proving that $n \leq m^{2} \leq 2n$ by induction

I am trying to prove that there exists a perfect square between a natural number and its double, and I am trying to prove it by induction. Here is my proof so far, but I am kind of stuck. for $n=1$, ...