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
44 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 = \frac{a^{...
2
votes
2answers
57 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
vote
3answers
53 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
35 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
46 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 \left(\frac{1+\sqrt{5}}{2}\...
2
votes
2answers
51 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
41 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
2answers
77 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$$ ...
-1
votes
1answer
20 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^*$, $\...
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
vote
2answers
44 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\...
0
votes
1answer
54 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 Case:...
0
votes
1answer
48 views

Prove using induction that $\forall n \in \mathbb{N}$ $f(n) + g(n) = 1$

$$f(0) = 1\\ h(0) = 1\\ g(0) = 0\\ f(n + 1) = 1 − h(n)\\ h(n + 1) = 1 − g(n + 1)\\ g(n + 1) = f(n) $$ Prove using induction that $...
3
votes
2answers
45 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
0answers
54 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 ...
1
vote
1answer
40 views

An inequality with exponents, factorials and nth roots!

Problem: Prove for natural numbers $n > 2$, $$(\sqrt{2!}-1)((3!)^{\frac{1}{3}}-\sqrt{2!})\cdots(((n+1)!)^{\frac{1}{n+1}}-(n!)^{\frac{1}{n}}) < \frac{n!}{(n+1)^n}$$. I am unable to do this one. ...
1
vote
0answers
117 views

Inequality for symmetric $n \times n$-matrix with non-negative elements.

Let us consider a symmetrix $n \times n$ - matrix $A$ with non-negative elements $a_{ij} \geq 0$. Furthermore, we look at a non-negative vector $x \in \mathbb{R}^n$ with $x_i \geq 0$. Then we want to ...
2
votes
1answer
65 views

Proove $3^n$ divides $a(n)$ for all integers $n\ge 1$

Q. Define a sequence of integers $a_1$, $a_2$, $a_3$... $a_1=3$, $a_2=18$ and $a_n=6a_{n-1} - 9a_{n-2}$ for each integer $n\ge 3$. Prove by strong induction that $3^n$ divides $a_n$ for all integers ...
2
votes
5answers
403 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
32 views

If $a, b \in \mathbb{N}$ are relatively prime, show that, for any $k \in \mathbb{N}$, $a^k$ and $b$ are relatively prime.

I am given this statement: $a, b \in \mathbb{N}$ are relatively prime if and only if there exist integers $\alpha, \beta$ such that $1 = \alpha \cdot a + \beta \cdot b$. I know that $\gcd(a^k,b) = 1$ ...
1
vote
3answers
71 views

Use induction to prove that that $8^{n} | (4n)!$ for all positive integers $n$

Use induction to prove that that $8^{n} | (4n)!$ for all positive integers $n$ So far I have: Base case (n = 1) = $8^{1} | (4(1))!$ = $8 | 24$ which is true. Induction Step: $8^{n + 1} | (4(n + 1))...
0
votes
1answer
43 views

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

Do I have to use induction to prove this? I tried this: Basis Step $n = 1$ $2^1 = O(1!)$ $2 = O(1)$ This doesn't work and neither does 0.
0
votes
1answer
63 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)! ...
0
votes
1answer
15 views

Prove sequence defined by recurrence relation using induction

Confused at this question, from what I gather strong induction is necessary here to prove this but the algebraic step after the Inductive Hypothesis is where I'm not too sure. Basis: 2 <= a1 = 2 &...
3
votes
0answers
73 views

Every skew-symmetric matrix has even rank [duplicate]

Let $F$ be a field where $char(F)\neq2$ and let $A$ be a skew-symmetric matrix over $F$. Prove that rank of $A$ is even. I think the best way to prove it, is using induction on size of $A$. for $n=...
0
votes
3answers
58 views

Proof by mathematical induction that $2^n < (n+2)!$ for all $n\ge 0$

I have been trying to get this.. For hours. Prove by M.I. that $2^n < (n+2)!$ for $n\ge0$ Here is what I am doing: Base case checks out at $n=0$ Make assumption for: $n=k$ Want to prove: $2^...
1
vote
0answers
31 views

prove that for any pair of natural, there is a power of 2 that separates the pair of natural

i need to prove that: $$ \forall i,j \in \{1, \_ ,N \} \subset \mathbb{N} \ \exists k \in \mathbb{N} / (r_{2^k}(i) \leq 2^{k-1} \wedge r_{2^k}(j) > 2^{k-1})\vee (r_{2^k}(i) > 2^{k-1} \...
2
votes
2answers
44 views

How to show using proof by induction: $\sqrt[n]{n!} \leqslant \frac{n+1}{2}, n \in \mathbb{Z}^+$

I'm having quite a few problems with the following proof by induction question: $$\sqrt[n]{n!} \leqslant \frac{n+1}{2}, n \in \mathbb{Z}^+$$ I manage to do the easy parts of the base step ($n=1$) ...
5
votes
2answers
183 views

$n\times n$ chessboard game with coins

The rows and the columns of an $n\times n$ chessboard are numbered $1$ to $n$, and a coin is placed on each field. The following game is played: A coin showing tails is selected. If it is in row $x$ ...
0
votes
3answers
76 views

Prove by strong induction that $3^n$ divides $a_n$ for all integers $n \ge 1$

Let $a_1 = 3, a_2 = 18$, and $a_n = 6a_{n-1} − 9a_{n-2}$ for each integer $n \ge 3$. Prove by strong induction that $3^n$ divides $a_n$ for all integers $n \ge 1$ I've done the base step and ih ...
1
vote
2answers
68 views

Proving a Formula for a Definite Integral by Induction.

I've been on this for hours and would really appreciate some help, I'm new to induction in general, so sorry if this is a simple question. Let $ I_{N}=\int_{0}^{1}x^{n}\sqrt{1-x}dx $ Prove that $I_{...
0
votes
1answer
24 views

prove by induction: power/chain rule combination

Use the product rule and induction (but NOT the chain rule) to prove that if $f(x)$ is a differentiable function, then for any $n \ge 1$, $d/dx (f(x))^n = n(f(x))^{n−1} * f'(x)$. I have: base case $n=...
1
vote
2answers
65 views

Proof by Induction

I am attempting to prove by induction that the algorithm calculates the cube of a number, I can't for the life of my grasp it. I was wondering if someone could help me please. The question is: A ...
2
votes
1answer
41 views

Help With an (structural) Induction proof on ordered pair

This is a Structural Induction proof. I don't want the solution, just some help in the right direction. I know normally in structural induction proofs, you use your base case, with the recursive step ...
0
votes
1answer
18 views

Induction with associative binary operation

Let * be an associative binary operation on a set 'A' with identity element e. Let 'B' be a subset of 'A' that is closed under *. Let b1, b2, b3, ... bn ∈ B. Prove that b1 * b2 * b3... bn ∈ B. ...
0
votes
5answers
47 views

Proofs and definitions.

I am a first-year university student and even with help from tutors I have a difficult time understanding proofs. In particular I notices that when using proofs (be it by induction or contradiction) ...
1
vote
2answers
46 views

“Right” way to get from $P(n)$ to $P(n+1)$ in an inductive step?

I'm reading a Math lecture note on mathematical induction, and in it, the author condemns a way of concluding that $\ P(n) \implies P(n+1)\ $, which is done by assuming $\ P(n+1)$, making a few ...
0
votes
1answer
25 views

Induction proof of a Recurrence Relation?

Consider the following recurrence equation obtained from a recursive algorithm: Using Induction on n, prove that: So I got my way thru step1 and step2: the base case and hypothesis step but I'...
0
votes
1answer
27 views

prove by induction: $x_n=a^nx_0+b(1+a+\cdots+a^{n-1})$ given $f(x)=ax+b$ with initial value $x_0$

prove by induction: $x_n=a^nx_0+b(1+a+\cdots+a^{n-1})$ given $f(x)=ax+b$ with initial value $x_0$ I'm fine with base case and hypothesis, but having some problems showing that it is true for $P(n+1)$ ...
1
vote
2answers
50 views

Proof by Induction: Number of bit strings of length $n$ starting with a 1 or ending with a 0 [duplicate]

We showed that the number of bitstrings of length $n$ that begin with a 1 or end with a 0 (or both) is $3 \cdot 2^{n−2}$. Sketch a proof by induction for this. Would we prove this by manipulation? I'...
1
vote
1answer
31 views

Induction proof (bitstring length)

Theorem : The number of bitstrings with the length $x$ that begin with $1$ and/or end with $0$ is $3 \times 2^{x-2}$. I know there are easier ways to prove this but I must figure out how to do it ...
2
votes
1answer
47 views

Induction Proof: If $B \subseteq A$, then $|B| \leq |A|$.

Prove by induction that if $A$ is a finite set and $B$ is a subset of $A$, then $|B|≤ |A|$. I can prove the base case with $n=0$ easily, but am stuck as to how to proceed from there.
1
vote
1answer
34 views

how do I prove this by induction? (recursion)

The terms are given recursively: $P_0=3$ $P_1=7$ and $P_n = 3P_{n-1}-2P_{n-2}$ for $n\ge2$ What should I assume and what step proves that $P_n=2^{n+2}-1$ is a closed form of the sequence. Suppose $...
0
votes
6answers
33 views

Discrete math induction proof (divisibilty) [duplicate]

How to show that $10^n -(-1)^n$ is always divisible by $11$ through proof of induction?
2
votes
1answer
43 views

Algebra not working out

I'm trying to prove $$\sum_{j=1}^{n-1} jx^j = \frac{x-nx^n+(n-1)x^{n+1}}{1-x^2}$$ holds for all positive integers $n$ and real $x\ne \pm 1$ by induction. In the inductive step I get $$\begin{align}\...
0
votes
1answer
22 views

Infimum and supremum of finite ordered subsets

I am currently taking an introductory proofs course, and I have come across this problem. It's asking to prove the following: Let $S$ be an ordered set. Let $A$ be a non-empty finite subset. Then ...
-1
votes
2answers
60 views

How can I prove by induction that this is a closed form of the Fibonacci sequence? [duplicate]

How can I prove by induction that this is a closed form of the Fibonacci sequence? $$F_n=\frac1{\sqrt5}\left(\frac{1+\sqrt5}2\right)^{n+1}-\frac1{\sqrt5}\left(\frac{1-\sqrt5}2\right)^{n+1}$$ I've ...
0
votes
2answers
32 views

Prove by induction: the coefficients of (a+b) to the power of n are the same if turned into a number as 11 to the power of n

Proof by induction that the coefficients of $(a+b)^n$ in order, if place as a number, the first coefficient being having the biggest place value, and each number lowers in place value, are equal to ...
0
votes
0answers
17 views

Proving a property of Harmonic sum by induction

Let $H_n = \sum_{j=1}^n \frac 1j$. I'm trying to prove that $H_{2^n}\ge 1+\frac n2$ using the principle of mathematical induction. The base step was no problem but I'm stuck on the inductive step: $...