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
10 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
44 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
26 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 ...
5
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
71 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
23 views

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

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
60 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
51 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
81 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
26 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
29 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
551 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
586 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
28 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
33 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
54 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
42 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
46 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 ...
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
32 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?
0
votes
1answer
80 views

Why is Mathematical Induction used to prove solvable inequalities?

As a first year undergrad student I've seen problems where solvable inequalities need to be proven to hold in a specific domain using Mathematical Induction. My question is, if the inequalities are ...
1
vote
2answers
38 views

Predicates and Indirectly Proving the last step of Mathematical Induction

Okay to illustrate this problem, I'm going to need to give an example, and go through the steps of Mathematical Induction to show where my question is aimed at. Example : Prove that $$ n^2 \geq 2n + ...
1
vote
2answers
42 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
47 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 ...
1
vote
2answers
37 views

Expanding a Proof of Induction on $\Bbb N $ to $\Bbb Q $ (Linear Algebra)

My problem is the following: I have an $\Bbb R$ Vectorspace called $V$ and had to show via induction that $\langle nv, w \rangle=n \langle v, w \rangle$ for $v,w \in V$ and $ n\in \Bbb N$. (it's not ...
5
votes
7answers
313 views

Prove that if $n^2$ is divided by 3, then also $n$ can also be divided by 3.

$n\in \Bbb N$ Prove that if $n^2$ is divided by 3, then also n can also be divided by 3. I started solving this by induction, but I'm not sure that I'm going in the right direction, any ...
3
votes
3answers
2k views

Base cases in strong induction

In strong induction, the inductive hypothesis assumes that for all k, P(k) is true. A lot of the proofs I've come across just take this as an assumption. Why then, in some other cases, is it ...
5
votes
2answers
65 views

Proof by induction, 1 · 1! + 2 · 2! + … + n · n! = (n + 1)! − 1

So I'm supposed to prove that $$1 · 1! + 2 · 2! + \dots + n · n! = (n + 1)! − 1$$ using induction. What I've done Basic Step: Let $n=1$, $$1\cdot1! = 1\cdot1 = 1 = (n+1)!-1 = 2!-1 = 2-1 = 1$$ ...
0
votes
1answer
61 views

Prove that $n! = O(n^n)$

I thought $n^n$ was greater than $n!$. How would I go about proving this? I have this so far: Assume that $P$($n$) is true $n!$ = O($n^n$) Assume that $P$($n+1$) is also true $(n+1)! ...
3
votes
2answers
44 views

Proving $\sum_{i=0}^n \binom{n}{i} = 2^n$ by math induction

I am having some trouble using math induction to prove the following problem: $$\sum_{i=0}^n \binom{n}{i} = 2^n$$ Where n $\geq$ 0 I know the first thing with math induction is substitute the base ...
1
vote
2answers
43 views

Proving $1 \cdot 2 + 2 \cdot 3 + \cdots + n(n + 1) = 2\binom{n + 2}{3}$by math induction?

I am working on a problem, but I don't know whether or not to use math induction on it. Here's the problem: Prove that for all integers $n \geq 1$, $$1 \cdot 2 + 2 \cdot 3 + \cdots + n(n + 1) = ...
2
votes
5answers
397 views

Divisibility via Induction: $8^n\mid (4n)!$ [duplicate]

I have to prove by induction the following fact: Show that $(4n)!$ is divisible by $8^n$. My stab at the solution: I have a slightly bad feeling about this solution and I would like if someone ...
0
votes
1answer
85 views

Show that $(a_1\cdot a_2\cdot …\cdot a_n)^\frac 1n \leq (a_1+…+a_n)/n$ [duplicate]

Sorry if it is sort of hard to read so here it is in words. Show that the nth root of the product of n terms is less than or equal to the sum of n terms divided by n. Our instructions are to use a ...
-1
votes
1answer
15 views

Prove using induction that $\forall x \in \Sigma^*$, $\operatorname{rev}(\operatorname{rev}(x)) = x$

Let $\Sigma$ be an alphabet. Assume that $\forall x, y \in \Sigma^*$, $\operatorname{rev}(xy) = \operatorname{rev}(y)\operatorname{rev}(x)$ Prove using induction that $\forall x \in \Sigma^*$, ...
1
vote
0answers
44 views

Simple proof of part of master theorem

This is part of a homework assignment I'm having trouble with and would be thankful for a little hint. Let $a>b>1,c>0 \in \mathbb{N}$ and $T: \mathbb{N} \to \mathbb{N}$ defined recursively ...
0
votes
1answer
44 views

Prove Using Induction: $\sum_{k=1}^{n} 1/k(k+1) = n/(n+1)$

The task at hand is to prove using induction that the following proposition holds for all $n \in \mathbb{N}$. $$P(n): \sum_{k=1}^{n}1/k(k+1) = n/(n+1)$$ Here is the proof I have thus far: Base ...