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

1
vote
2answers
27 views

Show that, for all $n > 0$, $A^n = {a^n\over a − b} (A − bI) + {b^n\over b − a} (A − aI)$.

Let $A ∈ M_{2×2}(\mathbb{C})$ be a matrix having distinct eigenvalues $a \neq b$. Show that, for all $n > 0$, $A^n = {a^n\over a − b} (A − bI) + {b^n\over b − a} (A − aI)$. I'm trying to prove ...
2
votes
1answer
46 views

Let $A ∈ M_{2×2}(\mathbb{C})$ be a matrix having a unique eigenvalue $c$. Show that $A^n = c^{n−1}[nA − (n − 1)cI ]$ for all $n > 0$.

Let $A ∈ M_{2×2}(\mathbb{C})$ be a matrix having a unique eigenvalue $c$. Show that $A^n = c^{n−1}[nA − (n − 1)cI ]$ for all $n > 0$. I'm doing induction for this, the base step when $n=1$ gives ...
1
vote
1answer
50 views

Multiplying products of $p_1,p_2,\ldots,p_n$ gives a square.

Given $n+1$ ($n\ge 4$) arbitrary products of primes $p_1,p_2,\ldots, p_n$, prove multiplying some of the products gives a square. E.g., for $n=4$: $\{p_1,p_2,p_3,p_4,p_1p_3\}$ satisfies the ...
3
votes
2answers
24 views

Show that the sequence $(x_n)=c^{\frac{1}{n}}$ is increasing for $0 < c < 1$.

Show that the sequence $(x_n)=c^{\frac{1}{n}}$ is increasing for $0 < c < 1$. I am trying to do this using induction. We see for the base case that $x_1 = c$ and $x_2 = c^{0.5}$, so clearly $...
4
votes
1answer
79 views

Prove using induction that from a set of $n+1$ numbers from $1..2n$, at least one number will evenly divide another.

Given a set of $n+1$ numbers out of the first $2n$ natural numbers, $1,2,\ldots,2n$, prove that there are two numbers in the set, one of which divides the other. I can't tell if I'm reducing the ...
0
votes
2answers
53 views

Finding a closed form for the recursively defined function using the substitution method.

This is a question from a problem set I had to do for one one of my courses. The following recursively defined function is given \begin{equation*} T(n) = \begin{cases} 1, & if \ n=0 \\ 4, & ...
0
votes
1answer
36 views

Prove recurrence relation using mathematical induction

solve recurrence relation $a_n = a_{n–1} + 12 a_{n–2}$, where $a_0 = 1$ and $a_1 = 11$ and Verify, using Principle of Mathematical Induction, that $a_n = (-1)(-3)^n + (2)(4^n)$. ans: i have done so ...
1
vote
1answer
50 views

Expand the summation (university) [closed]

Expand the summation $$\sum^{n}_{i=0}i\times i! = $$ I am studying for an exam, I have no idea what this question means.
0
votes
2answers
61 views

Induction proof fibonacci numbers

I need to prove the following with induction: n∑i=1 F(2i-1) = F(2n) for all n >= 1 I am stuck in my inductive step: n∑i=1 F(2i-1) = n∑i=1 F(2i-1) + F(2(n + 1) -1) = F(2n) + F(2(n + 1)-1) =...
1
vote
2answers
74 views

Proof by induction $\frac{1}{1^2} + \frac{1}{2^2} + \cdots + \frac{1}{n^2} < 2$

Proof by induction $\frac{1}{1^2} + \frac{1}{2^2} + \cdots + \frac{1}{n^2} < 2 \ \ \ n \in \mathbb{N}$ So for $n=1$ $$ 1 < 2$$ For $n > 1$ Assumption: $$\frac{1}{1^2} + \frac{1}{2^2} + \...
7
votes
2answers
209 views

upper bound of a double sequence

Let $\{ a_{k,m} \}$ be a doublely indexed sequence of positive numbers satisfying: $a_{1,n}\leq \frac{1}{n+1}\quad $ and $\quad a_{k,m} \leq \frac{1}{m+1}(a_{k-1,m+1}+L a_{k-1,m+2})\quad \quad (1)$ ,...
2
votes
1answer
48 views

Proving some identities in the set of natural numbers without using induction…

I'm not sure how to prove some of the identities without using induction, for example: $$1+2+3+...+n=\frac{n(n+1)}{2}$$ $$1^2+2^2+...+n^2=\frac{n(n+1)(2n+1)}{6}$$ $$1^3+2^3+...+n^3=(\frac{n(n-1)}{2})^...
1
vote
1answer
105 views

Prove by induction $\sum _{i=1}^n\left(-1\right)^{i+1}\:\binom{n}{i}\:\frac{1}{i}=1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n}$ [duplicate]

$$\sum _{i=1}^n\left(-1\right)^{i+1}\:\binom{n}{i}\:\frac{1}{i}=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}$$ Can someone give me a hint on how to give the proof, I am stuck when I am proving it for p(n+...
2
votes
1answer
35 views

Proof by induction: $ 2^n \ge n^2$ for $n\ge4$ [duplicate]

The first part is clear but in the second I did this: $2^{n+1}=2^n\cdot 2 \ge n^2\cdot 2=n^2+n^2=n^2+n\cdot n\ge n^2+n\left(2+\frac{1}{n}\right)=(n+1)^2$ I'm not sure if I the assumption: $n\ge 2+(...
0
votes
3answers
121 views

Proving a closed-form recurrence by induction

Find the closed form for the following, then prove by strong induction: $$T(n) = \begin{cases} 1\quad &\text{ if } n = 0 \\ 11\quad &\text{ if } n = 1 \\ T(n-1) + 12T(n-2) & \text{ ...
0
votes
1answer
38 views

Recursive/Strong Induction

Suppose that $a_0, a_1, a_2, \dots$ is a sequence defined as follows. $$a_0 = 2, a_1 = 4, a_2 = 6 \text{, and } a_k = 7 a_{k-3} \text{ for all integers $k \ge 3$.}$$ Prove that $a_n$ is even for all ...
1
vote
1answer
54 views

Prove if $f$ is class $C^r$, then $f^{-1}$ is of class $C^r$

Suppose that $f:(a,b)\rightarrow$ is differentiable and that $f'$ is never zero. By the inverse-function theorrem, $f$ is a bijection from $(a,b)$ onto an interval $(c,d)$, the function $f^{-1}:(c,d)\...
0
votes
2answers
101 views

Trees with no vertex of degree 2 have more leaves than internal nodes

There is a question asked by portal about Tree having no vertex of degree 2 has more leaves than internal nodes so we want to prove this claim by induction and an answer from Micheal Biro suggested ...
1
vote
6answers
163 views

Proving that $64$ divides $3^{2n+2}+56n+55$ by induction

Let $n ≥ 0$ be an integer. Prove by induction: 64 divides $3^{2n+2} + 56n + 55$ general expression: $3^{2n+2} + 56n + 55 = 64m$ 1st I substitute $P(0)$ and it gives me true: $9+55 = 64$ (if m = 1 ...
0
votes
1answer
29 views

Proof by induction for inequality

Suppose $L:(0,\infty)\rightarrow \mathbb{R}$ is differentiable, that $L(1)=0$, and that $L'(x)=1/x$ for all $x>0$. Show that $L(2^n)>n/2$ for all $n\in N$. Based off of a hint I am to use the ...
1
vote
2answers
36 views

Induction proof I'm having trouble with: $1+x+x^2+x^3+…+x^n = \frac{1-x^{n+1}}{1-x}$

So I'm being asked to use induction to prove that for every $x\in\{a\ |\ a\in R, a\neq 1\}$ and for every $n\in N$ $$ 1+x+x^2+x^3+...+x^n = \frac{1-x^{n+1}}{1-x} $$ I have no trouble proving it for $...
1
vote
2answers
81 views

Question regarding proof by Induction

A vending machine cannot return coins as change, but only five-cent and eight-cent stamps. For a particular k, though, we can prove by induction that the machine can make every number of cents that ...
0
votes
2answers
124 views

Proving a mangled graph to be connected.

In MIT's 6.042J course, there is a question in assignment 5 problem 3 c. An n-node graph is said to be mangled if there is an edge leaving every >set of n/2 or fewer vertices. Again, as a special ...
0
votes
0answers
30 views

proof that $n! \leq (\frac{n+1}{2})^n$ [duplicate]

How do I prove the following statement using induction? $(n \in \mathbb{N})$ $$n! \leq (\frac{n+1}{2})^n$$ So for $n = 1$ it is true, since $1 \leq (\frac{2}{2})^1$. So now: Assumption: $n! \leq (\...
0
votes
3answers
55 views

proof that $n^2 + 2n \leq 5^n $

How do I prove the following statement using induction? $(n \in \mathbb{N})$ $$n^2 + 2n \leq 5^n $$ So for $n = 1$ it is true, since $1 + 2 \leq 5$. So now: Assumption: $ n^2 + 2n \leq 5^n $ ...
-1
votes
3answers
67 views

Upper estimate for partial sums of the series $\sum 1/n^3$

I'm looking for a proof of: $$1 + {1\over 8} + {1 \over 27} + \dots + {1 \over n^3} < 1.5 − {1 \over n}$$ for all integers $n>2$. I have been working on proof by mathematical induction for a ...
1
vote
1answer
218 views

Flipping bits and crossing strings induction problem.

Consider a binary string consisting of n bits, where n ≥ 1. We are allowed to perform the following operation: we can replace a 1 by a x, and when we do that we must flip the two bits immediately ...
0
votes
1answer
158 views

2^m marbles in multiple boxes.

Let m be a non-negative integer. Suppose $2^m$ marbles are separated into several boxes. At each step we are allowed to do the following operation: Pick two boxes, say box A with p marbles and box B ...
0
votes
2answers
68 views

Prove: $\frac{(2n)!}{n!(n+1)!}\in \mathbb{N}, \forall n\in\mathbb{N}$

Prove: $\frac{(2n)!}{n!(n+1)!}\in \mathbb{N}, \forall n\in\mathbb{N}$ I used induction, for $n=k$ assume that $\frac{(2k)!}{k!(k+1)!}\in \mathbb{N}$ For $n=k+1$ $\frac{(2k+2)!}{(k+1)!(k+2)!}\in \...
0
votes
2answers
108 views

Induction proof of exponential and factorial inequality

I'm trying to find a proof for the following statement, using mathematical induction: $$ (\forall n\in \mathbb N-\{0\}) n^n \ge n! $$ But I always get to a dead-end. I've done the basis step, for $...
1
vote
2answers
52 views

Prove by induction: $\sum\limits_{k=1}^{n}(-1)^{k+1}{n\choose k}\frac{1}{k}=1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n}$

$\sum\limits_{k=1}^{n}(-1)^{k+1}{n\choose k}\frac{1}{k}=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}$ For $n=1$ equality is true. For $n=m$ $m-{m\choose 2}\frac{1}{2}+...+(-1)^{m+1}\frac{1}{m}=1+\frac{...
0
votes
1answer
23 views

Is this proof of the worst-case performance of linear search correct?

I am sorry for the triviality of this question, but is this proof of the worst-case complexity of linear search correct? Claim. Let $L$ be a list of length $n$ and $k$ a target value in $L$. Then in ...
0
votes
1answer
48 views

how to solve this induction problem?

An m × n array A of real numbers is a Monge array if for all i, j , k and l such that 1 ≤ i < k ≤ m and 1 ≤ j < l ≤ n, we have A[i,j] + A[k,l] ≤ A[i,l] + A[k,j] In other words, whenever we pick ...
1
vote
4answers
96 views

Prove by induction: $\sum\limits_{k=1}^{n}sin(kx)=\frac{sin(\frac{n+1}{2}x)sin\frac{nx}{2}}{sin\frac{x}{2}}$

$\sum\limits_{k=1}^{n}sin(kx)=\frac{sin(\frac{n+1}{2}x)sin\frac{nx}{2}}{sin\frac{x}{2}}$ Base case: For $n=1$ $sinx=\frac{sinx\cdot sin\frac{x}{2}}{sin\frac{x}{2}}=sinx$ Induction hypothesis: For $...
1
vote
1answer
45 views

Prove by induction: $\sum\limits_{k=1}^{n}\frac{1}{2^k}\tan\frac{x}{2^k}=\frac{1}{2^n}\cot\frac{x}{2^n}-\cot x,x\neq k\pi,k\in \mathbb{Z}$

$\sum\limits_{k=1}^{n}\frac{1}{2^k}\tan\frac{x}{2^k}=\frac{1}{2^n}\cot\frac{x}{2^n}-\cot x,x\neq k\pi,k\in \mathbb{Z}$ Base Case: For $n=1$, $\frac{1}{2}\tan\frac{x}{2}=\frac{1}{2}\cot\frac{x}{2}-\...
-1
votes
2answers
52 views

Summation proof- struggling to see a way to prove

I have found that the summation attached gives a general value of 1/(n+1) for the first few values of n=0,1,2,3.... I would like to prove that this is true for all n and I assumed that the best way ...
4
votes
2answers
73 views

Recurrence relationship

How do you solve the following recurrence relationship? $$x_{n} = \frac{x_{n-1}}{1 + x_{n-1}}$$ where $$ x(0) = 1 $$ I know the answer is $$ x_n = \frac{1}{n+1}$$ I solved it by induction. But I ...
1
vote
4answers
33 views

Basic Induction

Can someone give me a hint on how to solve this? Prove that $3^{(3n+4)} + 7^{(2n+1)}$ is divisible by 11 for all natural numbers n. So far I've got Base P(1): $3^{(3(1)+4)} + 7^{(2(1)+1)} = 2530$, ...
1
vote
1answer
68 views

Induction proof for integrals [duplicate]

I am having issues with proving the second step, and have been told that it would be best to approach this question by induction. I have manages to get this far: $$\left(\int_{a}^b g(x)f(x)=\frac{(-1)...
1
vote
0answers
35 views

Upper bound on a sequence after a finite number of steps

i need to find an upper bound (as tightest as possible) of the following recurrence for $\mu^{(j)}$ $$ \left\{ \begin{array}{l} t^{(j-1)} = 2 \mu^{(j-1)} - \nu & j \geq 1\\ \mu^{(j)} = \begin{...
0
votes
0answers
42 views

∀n∈ℕ:∑(-1)^(k+1)(1/k) [from k=1 to 2n] = ∑1/(n+k) [from k=1 to n] [duplicate]

Prove by induction: $$ \sum_{k=1}^{2n}(-1)^{k+1}\frac{1}{k} = \sum_{k=1}^{n}\frac{1}{n+k} $$ I start with (using $n = t+1$): $$ \sum_{k=1}^{2t+2}(-1)^{k+1}\frac{1}{k}=... $$ but after expanding and ...
0
votes
0answers
25 views

Given $T_n = \frac {1}{3}(2^{n+1} + (-1)^n)$ for $n \ge 1$ prove for $T_{n+1}$

Consider: $$Q_1(x_1) := x_1$$ $$Q_2(x_1,x_2) := (x_1\rightarrow x_2)$$ $$Q_3(x_1,x_2,x_3) := ((x_1\rightarrow x_2)\rightarrow x_3)$$ $$Q_4(x_1,x_2,x_3,x_4) := (((x_1\rightarrow x_2)\rightarrow x_3)...
0
votes
2answers
57 views

Prove that $im(T^{k+1}) ⊆ im(T^k)$ for every non-negative integer $k$ for any linear transformation $T: R^n → R^n$

Prove that $im(T^{k+1}) ⊆ im(T^k)$ for every non-negative integer $k$ for any linear transformation $T: R^n → R^n.$ I planned to try and prove this by induction, but I'm very unsure where to even ...
0
votes
0answers
11 views

$\forall_{q > 1}\ \forall_{k \in \mathbb{N}}\ \exists _{c > 0}\ \forall_{n \in \mathbb{N}}\ q^n \geq cn^k$

$\forall_{q > 1}\ \forall_{k \in \mathbb{N}}\ \exists _{c > 0}\ \forall_{n \in \mathbb{N}}\ q^n \geq cn^k$ So $\frac{q^n}{n^k} \geq c$ I would try induction but don't know where to start. How ...
1
vote
2answers
47 views

Show by induction: $(1+\frac{1}{n})^{n}<n$

Show by induction that for all natural numbers n>3 $(1+\frac{1}{n})^n<n$ Let $(1+\frac{1}{n})^n<n$ be true ! We show that $(1+\frac{1}{n+1})^{n+1})<n+1$ $(1+\frac{1}{n})^n(1+\frac{1}{n})&...
0
votes
0answers
40 views

Prove the following with Induction

$$\sum_{j=0}^d (s-1)^j \le s^d $$ for all $ s \ge 1 $ and $ d \ge 0 $, where $ s$ and $d$ both are natural numbers. I have been trying to do this with induction for a while, I have also tried to use ...
0
votes
2answers
56 views

Mathematical Induction Problem solving [duplicate]

$1^3$ + $2^3$ + $2^3$ + ... + $n^3$ = ($1 + 2 + 3 + ... + n)^2$ I start with $P(1)$ and get $1 = 1$. Then I do it with $P(n+1)$ and I get stuck. $1^3$ + $2^3$ + $2^3$ + ... + $n^3$ + $(n+1)^3$ = ($...
2
votes
3answers
47 views

Proof by Induction (Inequality)

I'm given a inequality as such: $n! > n^3$ Where n > 5, I've done this so far: BC: n = 6, 6! > 720 (Works) IH: let n = k, we have that: $k! > k^3$ IS: try n = k+1, (I'm told to only work ...
0
votes
2answers
111 views
1
vote
3answers
57 views

Proof inequality and series using Induction

How can I prove that $$ \sum_{k=1}^n \frac{1}{k^2} ≤ 2 - \frac {1}{n} $$ using induction? I first tried to prove this for $P(1)$, so: $$ \sum_{k=1}^n \frac{1}{1^2} ≤ 2 - \frac {1}1 $$ is ...