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

4
votes
1answer
29 views

An inequality $\frac1{(n+1)^{1/(n+1)}}-\frac1{n^{1/n}}\le \frac1{n+1}$

I have graphed the functions $f,g:\mathbb{R^+}\to\mathbb{R}$ defined by $$f(x)=\frac1{(x+1)^{1/(x+1)}}-\frac1{x^{1/x}}\mbox{ and } g(x)=\frac1{x+1}$$ and it seems like $f(x)\le g(x)$ for all $x>0$. ...
2
votes
2answers
23 views

Prove that L is a sub-language of the CFG G by using induction. (CFG,Induction,School)

i am asking for help with a question from a course in Logic im reading at university. I am aware that this type of question is frequently asked here(i have looked at alot of other questions/answers) ...
0
votes
1answer
28 views

Prove inequality $\frac{a_1a_2…a_n}{(a_1+a_2+…+a_n)^n}\le \frac{(1-a_1)(1-a_2)…(1-a_n)}{(n-a_1-a_2-…-a_n)^n}$

Let $n\in \mathbb N, a_1,a_2, ...,a_n\in \left(0,\frac 12 \right]$. Prove inequality: $$\frac{a_1a_2...a_n}{(a_1+a_2+...+a_n)^n}\le \frac{(1-a_1)(1-a_2)...(1-a_n)}{(n-a_1-a_2-...-a_n)^n}$$ My ...
2
votes
2answers
30 views

Prove that if $n \in \mathbb{N}$ and $n \ge 2$, then $2^{n + 1} \le 3^n$.

Prove that if $n \in \mathbb{N}$ and $n \ge 2$, then $2^{n + 1} \le 3^n$. My method: If $n = 2$, $2^{n + 1} \le 3^n$ then $2^3 \le 3^2$ is $8 \le 9$, which holds for $n = 2$. $2^{k + 1} \le 3^k$ ...
1
vote
2answers
27 views

Use induction to prove that $2^n \gt n^3$ for every integer $n \ge 10$.

Use induction to prove that $2^n \gt n^3$ for every integer $n \ge 10$. My method: If $n = 10$, $2^n \gt n^3$ where $2^{10} \gt 10^3$ which is equivalent to $1024 \gt 1000$, which holds for $n = ...
0
votes
2answers
34 views

Use the rule for differentiating a product to prove that the derivative of $x^n$ is $nx^{n-1}$ for all $n∈N$.

I know the rule of differentiation, but to proving why the derivative is that is my problem. Should I be proving this question by induction because that's what I've been learning.
2
votes
3answers
37 views

Prove that $\sum_{k=1}^n \frac{1}{n+k} = \sum_{k=1}^{2n} \frac{1}{k}(-1)^{k-1}$ using induction [duplicate]

I'm trying to prove (using induction) that: $$\sum_{k=1}^n \frac{1}{n+k} = \sum_{k=1}^{2n} \frac{1}{k}(-1)^{k-1}.$$ I have found problems when I tried to establish an induction hypothesis and ...
31
votes
14answers
4k views

Why doesn't mathematical induction work backwards or with increments other than 1?

From my understanding of my topic, if a statement is true for $n = 1,$ and you assume a statement is true for arbitrary integer $k$ and show that the statement is also true for $k + 1,$ then you prove ...
2
votes
3answers
28 views

Induction to prove that for any $r \in \mathbb{R}$ such tht $r \notin (0,1)$ $\sum_{i=1}^n r^i-1 = \frac{(1-r^n)}{1-r}$ for all $n \in \mathbb{N}$.

Use induction to prove that for any $r \in \mathbb{R}$ such that $r \notin (0,1)$ $$\sum_{i=1}^n r^{i-1} = \frac{1-r^n}{1-r}$$ for all $n \in \mathbb{N}$. My method: Assume $$\sum_{i=1}^k r^{i-1} = ...
3
votes
3answers
47 views

An induction problem that I can't think of an approach.

Prove that if $n$ people are standing on line at a ticket counter, and the first person on line is a woman and the last is a man, then somewhere on the line there is a man standing directly behind a ...
2
votes
2answers
37 views

Prove by induction that $\sum_{k=1}^nk^p < (n+1)^{p+1}/(p+1), \quad n,p \in \mathbb{N}$

For $n=1$, we have at the left side $1^p$, and at the right side: $$ \frac{2^{p+1}}{p+1}\mathrm{~which~is } >1$$ so it holds for $n=1$, but how can we prove that $$ ...
0
votes
0answers
13 views

Symmetric Positive Matrix Diagonal Value relationships after Gaussian Elimination

Let $A\in\mathbb{R}^{n\times n}$ be a symmetric positive definite matrix. Let Gaussian elimination be carried out on $A$ without pivoting. After $k$ steps, $A$ will be reduced to the form ...
0
votes
2answers
43 views

Proving a $\cos(2nx)$ identity using induction

Prove that $\cos(2nx)=∑_{k=0}^n (-1)^k \dbinom{2n}{2k} \cos^{2(n-k)}(x)\cdot \sin^{2k}(x):=p(n)$ I'd start using induction, with $n=1$ we have: $$cos(2x)=\cos^2(x)-\sin^2(x)$$ True. Now assume ...
0
votes
5answers
44 views

Prove by induction: A tree on n≥2 vertices has ≥2 leaves

This is what I have. I'm pretty sure this is quite incorrect, but am I at least headed in the right direction? Base Case: $P(2)$: Tree on 2 vertices can only have one edge, the edge connecting the ...
-2
votes
2answers
26 views

proove that any postage greater than 17 can be made using 4 and 7 cent stamps

Please use strong induction for the problem. I know that regular induction doesn't work. I assume there is a proof by logic by simply saying that 18, 19 and 20 cents can be made using these stamps and ...
2
votes
3answers
50 views

Establish by mathematical induction that a set having $n$ elements has $2^n$ subsets.

I know the steps to an induction proof. The first step is to establish that $n=1$ is true. Then the second step is to assume that if we replaced $n$ by $k$, $2^k$ is true. For the third step, assuming ...
1
vote
1answer
30 views

Proof by strong induction combinatorics problem

$1(1!) + 2(2!) + 3(3!) + \dots + n(n!) = (n+1)! - 1$ How do we prove this by strong induction? I know how to do it with weak induction, but how would strong induction work with this problem?
0
votes
0answers
21 views

Proving running time with induction

I need to use induction to prove the run time of the given recurrences: $T(1) = c_1$ $T(n) = T(n-1) + c_2$ Well this is the first time Im doing induction on this kind of exercise - I would like ...
3
votes
1answer
36 views

Prove that in every WFF, there is a logical connective between every two atoms.

First, I have defined a well-formed formula as such: 1) Each atom is a WFF. 2) If φ is a WFF, so is ¬φ 3) If φ and ψ are WFFs, if ∗ is a binary connected (i.e., ∨,∧,→), then (φ∗ψ) is a WFF. What ...
0
votes
1answer
16 views

Proving Recurrence Relation By Forward Substitution

I'm having trouble understanding the inductive proof of the following recurrence relation by forward substitution. I get that were plugging in the value for our induction step into the relation but I ...
0
votes
2answers
53 views

$\sum_{k=1}^n 1/k - \log n$

I got this question : $$a_n = \sum_{k=1}^n \frac 1k - \log n$$ I proved that $\lim a_n $ exist. Now I have to prove: $$ 0<a_n-\lim a_n\le \frac 1n $$ for every $n \in \mathbb N$. I tried ...
3
votes
0answers
32 views

Delete some numbers in $x_1+x_2+…+x_n=y_1+y_2+…+y_m<mn$

Let $$x_1+x_2+...+x_n=y_1+y_2+...+y_m<mn,$$ where $x_i,y_i -$ positive integers. Prove that you can delete some terms (but not all) in the equation and equality remains true. My work so ...
6
votes
1answer
1k views

Combinatorics - Catalan numbers recursive function proof by induction help

I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number). For $n=1$ this is true. Assume it is true for $n=k$: ...
5
votes
2answers
72 views

Proof using induction: $n! > n^2$, for $n\geq4$

Proof using induction: $n! > n^2$, for $n\geq4$ Basis: For n = 4, we have: $4! > 4^2$ $24 > 16$ (TRUE) Inductive step: By the induction hypothesis: $k! > k^2$ $(k+1)k! > (k+1)k^2$ ...
-5
votes
0answers
33 views

Proof by induction of for the cardinality of finite sets A and B [closed]

Can someone please help me with this proof? Proof by induction that for finite sets, A and B, an injection $f: A \rightarrow B$ exists if and only if A is finite and $|A| \le |B|$.
2
votes
2answers
61 views

Why can we assume a statement is true for $n = k$, when using induction? [duplicate]

I know the principle of mathematical induction. The only thing that causes my confusion is that we suppose a statement is true for $n=k$ then we prove the statement is also true for $n=k+1$ but how ...
1
vote
0answers
31 views

Help understanding one of Euler's theorem in Number Theory [duplicate]

I am looking at two Euler's theorems in my textbook which are the following: If $p$ is prime and $a$ is any whole number, then $(a+1)^p - (a^p + 1) $ is evenly divisible by $p$. If $p$ is prime and ...
1
vote
2answers
52 views

Hint for prove $\forall n \in \Bbb N \sum _{i=1}^{n} \frac {1}{i!} \le 2 - \frac{1}{2^{n-1}}$?

I'm trying to prove the following inequality $\forall n \in \Bbb N$: $$\sum _{i=1}^{n} \frac {1}{i!} \le 2 - \frac{1}{2^{n-1}}$$ I'm doing it by induction. It's true for $P(1)$. So now I want to ...
0
votes
3answers
89 views

Prove $\phi^n = \phi F_n + \text{(another Fibonacci number)}$ using mathematical induction.

I need to prove the following equation using mathematical induction and using the phi values if necessary. $\phi^n = \phi F_n + \text{(another Fibonacci number)}$ In this proof, it is kind of hard ...
-7
votes
0answers
40 views

Mathematical proof by induction. [duplicate]

How to prove the following using mathematical proof by induction? $\phi^n = \phi\times F_n + F_{n-1}$ $\phi = 1 + \sqrt 5 /2$ Fn is the Fibonacci number. I tried solving this using induction but ...
-1
votes
2answers
29 views

By induction prove $\prod _{i=1}^{n} \frac{n+i}{2i-3} = 2^n (1 - 2n)$

I need to prove the following by induction. $\forall n \in \Bbb N$ $\prod _{i=1}^{n} \frac{n+i}{2i-3} = 2^n (1 - 2n)$ I know the steps to take but I'm failing to come to the right side of the ...
2
votes
0answers
30 views

Suppose that $a, b ∈ N$ are relatively prime. Prove that, for any $k ∈ N$, $a^k$ and $b$ are relatively prime.

Note: I've asked this question before, but this one offers a proposed solution and I'm checking for verification. $a$ and $b$ are relatively prime if the greatest common divisor of them is $1$. I am ...
0
votes
1answer
554 views

Induction to prove regular expression

Prove that is if S and T are any regular expressions over the one-letter alphabet, (for example: Σ = {a}), and if n is any natural, then the languages (ST)^n and (S^n)(T^n) are equal. I have to use ...
0
votes
1answer
39 views

proving the inequality $ (\frac{n}{e})^n \leq n! \leq en ( \frac{n}{e})^n$ by induction

I want to prove $ (\frac{n}{e})^n \leq n! \leq en ( \frac{n}{e})^n$ by induction. For this prove I want to use the inequality $(\frac{n+1}{n})^n < e <(\frac{n+1}{n})^{n+1}$. for $n=1$ the ...
1
vote
1answer
15 views

Solution check: summation inequality proof by induction

I'm not sure if what I've done works or if it's proof enough. (I need to prove that the inequality is true $\forall n \in \mathbb{N}$). $\sum_{i=n}^{2n} \frac{i}{2^i} \leq n$ $P(1)$ works. I assume ...
0
votes
0answers
17 views

Solve using math induction with steps. [duplicate]

$$\sum_{i=1}^{n+1} i2^i = n2^{n+2} + 2, \forall n \geq 0$$ Getting stuck.
1
vote
2answers
596 views

Prove through structural induction that a binary tree has an odd number of nodes

A full binary tree is a binary tree where every node has either 0 or 2 children. Prove that every non-empty full binary tree has an odd number of nodes. I dont know how to get started with this ...
1
vote
0answers
72 views

Why this proof is incorrect?

I have an exercise that I cannot really understand: Let $P(n)$ be a property over the naturals (i.e., $n \in N$). The induction axiom, taking $0$ for the base-case instance, is the formula: ...
1
vote
1answer
31 views

How to prove by induction that $\frac{a^n+b^n}{2}\geq\left(\frac{a+b}{2}\right)^n$?

I'm about to prove that for any $a,b>0$ and $n\in\mathbb{N},$ the inequality: $\frac{a^n+b^n}{2}\geq\left(\frac{a+b}{2}\right)^n$ holds. By induction I get: ...
0
votes
1answer
29 views

Strong Induction Proof of amounts of money

I am so confused about this kind of question which is referring to amounts of money. I know we should use strong induction to prove if we meet some questions asking you which amounts of money can be ...
1
vote
2answers
51 views

How can you prove this by strong induction?

The sequence $b_1,b_2,...$ is defined recursively as:\begin{align} b_1&=0;\\ b_2&=1;\\ b_n&=2b_{n-1}-2b_{n-2}-1 \ \text{for} \ n\geq3. \end{align} Prove that this means: $$\forall n\geq1: ...
2
votes
1answer
21 views

induction with 2 recursive sequnces

I'm having trouble solving this problem. I have relation for two sequences of natural numbers. $$a(n)+\sqrt3\cdot b(n)=\left(1+\sqrt3\right)^n$$ and I have to prove that recursions: ...
2
votes
4answers
2k 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} + ...
1
vote
2answers
38 views

Prove by induction that $I_n = \frac{4^{n+1}n!(n+1)!}{(2n+3)!}$

$I_n$ is defined as: $$I_n = \int_{0}^{1} \big[x^n \sqrt{1-x}\big] dx$$ Let $p(n)$ be the statement: $$I_n = \frac{4^{n+1}n!(n+1)!}{(2n+3)!}$$ Prove by mathematical induction $p(n)$ is true for n ...
2
votes
2answers
34 views

Induction proof of the identity $\cos x+\cos(2x)+\cdots+\cos (nx) = \frac{\sin(\frac{nx}{2})\cos\frac{(n+1)x}{2}}{\sin(\frac{x}{2})}$ [duplicate]

Prove that:$$\cos x+\cos(2x)+\cdots+\cos (nx)=\frac{\sin(\frac{nx}{2})\cos\frac{(n+1)x}{2}}{\sin(\frac{x}{2})}.\ (1)$$ My ...
1
vote
5answers
55 views

Prove $\sum _{k=2}^{n} k(k-1) {n \choose k}=n(n-1)2^{n-2}$ [duplicate]

Prove $$\sum _{k=2}^{n} k(k-1) {n \choose k}=n(n-1)2^{n-2}$$ Proof by induction: true for $n=2$. Assume true for $n$ and see if $n+1$ is true. $$\sum _{k=2}^{n} k(k-1) {n \choose k}=n(n-1)2^{n-2}$$ ...
0
votes
2answers
43 views

Prove that $(a^n - b^n) = (a-b) \sum_{i=1}^n a^{i-1} b^{n-i}$

Let it be $a, b \in\Bbb R$. Prove that $\forall n \in\Bbb N$, $(a^n - b^n) = (a-b) \sum_{i=1}^n a^{i-1} b^{n-i}$. Deduce the formula of the geometric sum: $\forall a ≠ 1, \sum_{i=0}^n a^i = ...
3
votes
3answers
49 views

Prove $b-a \le \sum^n_{i=1}(b_i-a_i)$ by induction

Show that if the closed interval $[a,b]$ is covered by finitely many open intervals $(a_1,b_1), ...,(a_n,b_n)$, then $$b-a \le \sum^n_{i=1}(b_i-a_i)$$. I know that $(a_1,b_1), ...,(a_n,b_n)$ form an ...
2
votes
2answers
56 views

Use induction to show $\sum_{j=1}^x (4j - 1) = x(2x+1)$

Here is what we are given Use induction to show that for all $x$ $\in$ $\mathbb{Z}^+$ $$\sum_{j=1}^x (4j - 1) = x(2x+1)$$ This is what I have done Sometimes I find sigma notation a little confusing ...
-1
votes
0answers
34 views

If $k$ is an odd Integer… [duplicate]

if $k$ is an odd integer prove that for any integer $n$>$0$, $1^k + 2^k + 3^k +....+ n^k$ is divisible by $n(n+1)/2$. Well it looks like induction would work, but I was not able to reach a conclusion ...