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
1answer
50 views

Mathematical induction proof problem: $\sum_{i=1}^{n-1} i(i+1) = \frac{n(n+1)(n-1)}3$

I am having difficulty proving the inductive hypothesis $(k+1)$ for the following statement: $$\sum_{i=1}^{n-1} (i(i+1)) = \frac{(n)(n+1)(n-1)}{3}$$ This is what I have so far: $$(Step \ 1) ...
0
votes
1answer
35 views

Given the recurrence $T_n = 2T_{n-1} - T_{n-2}$, prove by Induction that $T_n = n$

Given the recurrence$$T_n = 2T_{n-1}-T_{n-2},$$$$T_0=0$$$$T_1=1$$Prove by induction, that $T_n = n$. I have the first few steps worked out. Basis: $n = 1$$$T_1=1=n=1$$ Assume true for $n = ...
1
vote
1answer
46 views

Induction Proof $2 + 5 + 8 + 11 + \cdots + (9n - 1) = \frac{3n(9n + 1)}{ 2}$

I am looking for an induction proof... $$2 + 5 + 8 + 11 + \cdots + (9n - 1) = \frac{3n(9n + 1)}{2}$$ when $n \geq 1$. I know there are $3$ steps to this. 1) Check 2) Do $n = k$ 3) Do $n = k + 1$ ...
4
votes
1answer
31 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
27 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
29 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
31 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
38 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 ...
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} = ...
2
votes
2answers
38 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 $$ ...
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 ...
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 ...
-2
votes
2answers
27 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 ...
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 ...
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 ...
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?
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
33 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 ...
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 ...
-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 ...
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
3answers
91 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 ...
-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 ...
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
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: ...
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}$$ ...
3
votes
3answers
50 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 ...
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 = ...
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 ...
1
vote
3answers
52 views

Use induction to show $0< x_n < 3$ and find its limit

Q define a sequence by $x_1=1$, $x_{n+1}=3-\frac{1}{x_n}$ for all $n \in \mathbb{N}$ a) Use induction to show $ 0 < x_n < 3$ for all $n \in \mathbb{N}$, and <$x_n$> is monotone increasing ...
0
votes
1answer
33 views

Show the sequence [fn]= 1+(1/1!)+(1/2!)…+(1/n!) is increasing and bounded above by 3. [duplicate]

This is part of a question. In the end we are trying to show the sequence up above converges to e. I need to use math induction.
0
votes
1answer
15 views

Non inductive proof for square of odd integers [duplicate]

Can we argue that the square of every odd integer is of the form $8k+1$ using non inductive proof?
1
vote
2answers
43 views

Lucas numbers proof

I'm running through some example problems and encountered this one: Define a sequence of integers $L_n$ by $L_1=1, L_2=3, L_{n+1}=L_n+L_{n-1}.$ Show that $L_n = a\cdot ...
2
votes
2answers
48 views

Prove that the identity is true for all natural numbers [closed]

for the identity: $$\frac{n!}{x(x+1)(x+2)...(x+n)} = \frac{A_0}{x+0} + \frac{A_1}{x+1}+...+ \frac{A_n}{x+n}$$ prove $$A_k= (-1)^kC(n,k)$$ I think this might work by induction, but i am not able to ...