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
8answers
86 views

Prove by induction that $3^{3n+1} + 2^{n+1}$ is divisible by 5

How do I do this? I've tried using logarithms, factoring, but nothing seems to work.
0
votes
2answers
488 views

Induction proof using Pascal's Identity: $\binom{n}{0}+\binom{n}{i}+…+\binom{n}{n}=2^n$

Prove by induction that for all $n ≥ 0$: $\binom{n}{0}+\binom{n}{i}+....+\binom{n}{n}=2^n$ We should use pascal's identity Base case: $n=0$ LHS: $\binom{0}{0}=1$ RHS: $2^0=1$ Inductive step: ...
0
votes
0answers
34 views

Proof by induction- The sum of the cubes of the first n positive integers [duplicate]

I am having trouble with this proof by induction. The sum of the cubes of the first $n$ positive integers can be computed by the following formula: $\sum_{k=1}^{n}k^3= 1^3 + 2^3 + . . . + n^3 = \...
3
votes
1answer
177 views

prove inequality by induction — Discrete math

Prove by induction that $∀n ≥ 3$ : $n^{2} + 1 ≥ 3n$ So I know I need to find my base case, would it be: $n=3$ Then calculate the RHS and LSH RHS:$3(3)=9$ LHs: $3^{2} + 1= 10$ we see that the LHS is ...
4
votes
6answers
81 views

Prove by mathematical induction that $\forall n \in \mathbb{N}: 20~|~4^{2n} + 4$

Prove by mathematical induction that $\forall n \in \mathbb{N}: 20~|~4^{2n} + 4$ Step 1: Show that the statement is true for n = 1: $4^{2 \cdot 1} + 4 = 20$ Since $20~|~20$, the base case is ...
2
votes
2answers
66 views

How to use Induction with Sequences?

I have posted this similar question here, but with no hopes. I would just like to know: Most of the solution I have no issue with. Look at where they say: "Choose a representation $(n - 3^m)/2 = ...
1
vote
2answers
44 views

Showing that if $xf(x)=\log x$ for $x>0$ then $f^{(n)}(1)=(-1)^{n+1}n!\bigg(1+\dfrac12+\dfrac13+\ldots+\dfrac{1}{n}\bigg)$

Let $f(x)$ be a function satisfying $$xf(x)=\log x$$ for $x>0$. Show that $$f^{(n)}(1)=(-1)^{n+1}n!\bigg(1+\dfrac12+\dfrac13+\ldots+\dfrac{1}{n}\bigg),$$ where $f^{(n)}(x)$ denotes the $n$th ...
3
votes
2answers
66 views

Mathematical induction problem with inequality

I have the following problem where n is a positive integer $(n >= 1)$: Prove that $\frac{1}{2n}\le\frac{1*3*5*...*(2n-1)}{2*4*...*2n}$ I know that I must start with the basic step showing that $P(...
2
votes
1answer
105 views

Proving something about the sequence of powers of 3 mod 10. Oh boy

Given the sequence $t_0=3, t_1=3^3,...$ so that $t_{n+1}=3^{t_n}$, prove $t_{k+1} \equiv t_k \mod 10^n$ for all integers $n \leq k$ My work so far: I thought it was a pretty obvious case for ...
1
vote
3answers
46 views

How to prove $2^{n+1} * 2^{n+1} = (2^n*2^n)+(2^n*2^n)+(2^n*2^n)+(2^n*2^n)$

Below diagram is used as part of a proof of induction to prove that $E$ a way to tile a $2^n * 2^n$ region with square missing : What is the proof that $2^{n+1} * 2^{n+1}$ = $(2^n*2^n)+(2^n*2^n)+(...
1
vote
2answers
62 views

Proof by exhaustion:

We are given that a polynomial f(x) has integer coefficients. The coefficient of x^4 being 1. One root of it is ($\sqrt{2}+\sqrt3$). How do we find the other roots? I tried using long division, it ...
5
votes
6answers
140 views

Proving that $7^n(3n+1)-1$ is divisible by 9

I'm trying to prove the above result for all $n\geq1$ but after substituting in the inductive hypothesis, I end up with a result that is not quite obviously divisible by 9. Usually with these ...
1
vote
3answers
168 views

Using induction to study the sequence $\sqrt{6} , \sqrt{6 +\sqrt{6}}, \dots$

For the given sequence $\sqrt{6} , \sqrt{6 +\sqrt{6}},\sqrt{6+\sqrt{6+\sqrt{6}}} $ ... Use induction to show the sequence is bounded above by 3 Use induction to show $x_n $ is increasing Find the ...
0
votes
1answer
69 views

Proving a function by induction [duplicate]

Let $f(n)$ be the function defined by $$ f(n) = \frac 1{\sqrt{5}} \left[ \left(1+\sqrt{5}\over2\right)^n- \left(1-\sqrt{5}\over2\right)^n \right] $$ How do you prove that $f(n) = f(n+2) - f(n+1)$ ...
3
votes
3answers
107 views

Prove $k^2>k+1$ by induction

How would you prove that: $$n^2>n+1 \text{ for } n\ge2$$ using induction? Progress The base is clear, and after that I have assumed $n=k$ and I am trying to prove $(k+1)^2>k+2$ , but I ...
3
votes
2answers
85 views

Prove by mathematical induction that $\forall n \in \mathbb{N} : \sum_{k=1}^{2n} \frac{(-1)^{k+1}}{k} = \sum_{k=n+1}^{2n} \frac{1}{k} $

Prove by mathematical induction that: $$\forall n \in \mathbb{N} : \sum_{k=1}^{2n} \frac{(-1)^{k+1}}{k} = \sum_{k=n+1}^{2n} \frac{1}{k} $$ Step 1: Show that the statement is true for $n = 1$: LHS = ...
0
votes
2answers
203 views

Induction Question. Suppose there are n teams in a football league

how can i prove this Let n > 1 be an integer. Suppose there are n teams in a football league and every two teams have played against each other exactly once with no ties. Prove that it is possible to ...
0
votes
3answers
81 views

Prove that a sequence is increasing [duplicate]

A city's population in the $n^{th}$ year is denoted by $x_n$ (in millions). If, $\forall n \in \mathbb N^+$, we have: $x_1 = \frac34$, $x_{n+1} = 2x_n - x_n^2$, show that as $n \to \infty$, the ...
1
vote
2answers
123 views

Induction Proof: $\frac{1\cdot 3\cdots (2n-1)}{2\cdot 4\cdots (2n)} \geq \frac{1}{2n}$

Need help proving with induction that $\displaystyle \frac{1\cdot3\cdot5\cdot7...(2n-1)}{2\cdot4\cdot6\cdot8...\cdot2n} \ge \frac 1{2n}$ for all natural numbers $n$. I just can't even get started with ...
3
votes
2answers
87 views

Proving $2^n > (n+1)^2$ for $n\geq 6$ by induction.

So here is what I have to prove by induction: $2^n\gt(n+1)^2$ for $n\ge6$ So, first lets say $n=6$ $$2^6\gt(6+1)^2$$ $$64\ge49$$ Now, assume $n=k$ $$2^k\gt(k+1)^2\text{ for } k\ge6$$ Prove $n=...
0
votes
1answer
67 views

Let $f(x)=(x^2-1)^n$. Prove that for $r=0,1, … ,n$, $f^{(r)}(x)$ is a polynomial with value $0$ at no fewer than $r$ distinct points on $(-1,1)$.

Let $f(x)=(x^2-1)^n$. Prove that for $r=0,1, ... ,n$, $f^{(r)}(x)$ is a polynomial whose value is $0$ at no fewer than $r$ distinct points on $(-1,1)$. In other words, prove that $f^{(n)}(x)$. I ...
2
votes
2answers
92 views

Is this statement of Mathematical Induction correct?

Theorem: Principle of Mathematical Induction For each natural number $n$, let $P(n)$ be a statement. If $P(1)$ is true and $P(k) \Rightarrow P(k+1)$ for every $k \geq 2$ Then $P(n)$ is true for ...
1
vote
1answer
26 views

Validity of Induction for a Summation

To prove the binomial identity $$\sum_{m=k}^{n-1}\binom{m}{k} = \binom{n}{k+1}$$ will an inductive method on $n-1$ be valid? Specifically, if we prove the base case where $n-1 = 0$, to determine it ...
0
votes
1answer
60 views

Number Theory using an induction proof

Prove that the inequality $$\left(1+\frac{1}{n}\right)^n > \frac{9}{4}$$ holds for all integers $n$ beyond a certain point. I must show that it is true for all $n>3$. but I am having difficult ...
1
vote
2answers
49 views

Proof $\frac{a_n^2+a_{n+1}^2+1}{a_{n}a_{n+1}} $ is constant

I would appreciate if somebody could help me with the following problem: Question: Defined by $a_{1} =1,a_{2}=2$ and $a_n a_{n+2}=a_{n+1}^2+1(n\geq 1)$ Proof. $\frac{a_n^2+a_{n+1}^2+1}{a_{n}...
8
votes
3answers
197 views

Prove that $1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}$ for $n \in \mathbb{N}$.

Problem: Prove that $1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}$ for $n \in \mathbb{N}$. My work: So I think I have to do a proof by induction and I just wanted some help editing my proof. My attempt:...
2
votes
1answer
84 views

Peano's Axioms and Induction

I was reading Landau's Foundations of Analysis. He starts his construction of number systems by stating five axioms. My question is related to the fifth, the axiom of induction: Let there be given a ...
0
votes
0answers
2k views

If $s_{k,m}(n) =\sum_{i=n+1}^{kn+m} \frac1{i} $ show that for $k \ge 2m+1$, $s_{k,m}(n+1)>s_{k,m}(n)$ and $s_{k,m}(n+1)-s_{k,m}(n) <\frac1{n(n+1)} $

Let $s_{k,m}(n) =\sum\limits_{i=n+1}^{kn+m} \frac1{i} $. Show that, for $k \ge 2m+1$, $s_{k,m}(n+1)>s_{k,m}(n)$ and $s_{k,m}(n+1)-s_{k,m}(n) <\frac1{n(n+1)} $ so that $s_{k,m}(n) < s_{k,m}(...
0
votes
0answers
20 views

Fallacious proof with induction [duplicate]

my teacher gave the following as an example of a fallacious proof: We'll prove that a group of $n$ people are either all male or all female. For $n = 1$ The claim says that a group containing ...
-1
votes
1answer
117 views

How to prove the inductive step in this Mathematical induction problem?

Note: This problem is from Discrete Mathematics and Its Applications [7th ed, prob 6, pg 342]. Problem: a) Determine which amounts of postage can be formed using just $3$-cent and $10$-cent stamps.b)...
0
votes
2answers
40 views

Mathematical Induction - condition

Question: Prove that $n(n+1)(n+5)$ is always divisible by 3 using mathematical induction. Well it is quite obvious that P(1) is true. However, my question is if: $$3\lambda\frac{(k+2)(k+6)}{k(k+...
1
vote
3answers
92 views

Mathematical induction for inequalities

Prove by induction: $$\frac1{n+1} + \frac1{n+2} + \cdots +\frac1{3n+1} > 1$$ adding $1/(3m+4)$ as the next $m+1$ value proves pretty fruitless. Can I make some simplifications in the inequality ...
2
votes
2answers
81 views

How to come up with relation in induction hypothesis for strong induction

Note: This problem is from Discrete Mathematics and Its Applications [7th ed, prob 2, page 341]. Problem: Let $P(n)$ be the statement that a postage of n cents can ...
0
votes
2answers
55 views

Math Inequality using induction?

Prove that $\log_3\pi + \log_\pi 3 > 2$ without using log tables. I was thinking of using strong induction for something like this, but I find it a difficult thing to come by, especially giving ...
0
votes
1answer
505 views

How to show the inductive step of the strong induction?

Note: This problem is from Discrete Mathematics and Its Applications [7th ed, prob 2, pg 341]. Problem: Use strong induction to show that all dominoes fall in an infinite arrangement of dominoes if ...
2
votes
2answers
157 views

Verify the following by mathematical induction

Verify the following by mathematical induction: $${n \choose 0} + {n+1 \choose 1} + {n+2 \choose 2} + \cdots + {n+r \choose r} = {n+r+1 \choose r}$$ I need some help with this proof...I understand ...
0
votes
2answers
67 views

How to get $k^{k + 1} + k^k$ to equate $(k+1)^{k+1}$?

This is a problem from Discrete Mathematics and its Applications Let $P(n)$ be the statement that $n!<n^n$, where $n$ is an integer greater than $1$. $\quad(a)$ What is the ...
2
votes
2answers
43 views

How is $(n+1)(n+2) / 2$ derived in this induction step?

I'm attempting to understand in how to get from step1 to step2 : Step 1. $1+2+\cdots+n = n(n+1)/2 $ Step 2. Need to show $1+2+\cdots+(n+1)= (n+1)(n+2) / 2$ How is $(n+1)(n+2) / 2$ derived from ...
2
votes
0answers
25 views

Proving that step-wise function is $\mathcal C^{\infty}$

I'd like a proof verification of the following, please. I want to prove that $H: \Bbb R \to \Bbb R$ is of class $\mathcal C^{\infty}$, with $H$ defined by: $$H(x) = \left\{\begin{align} &h(x) = e^...
2
votes
3answers
99 views

Inductive proof, algebra step

I have to prove by induction that $$1^2+2^2+3^2+ \cdot \cdot \cdot + n^2 = {n(n+1)(2n+1)\over 6}$$ Base step: $$1^2 = {1(1+1)(2\bullet1 +1)\over 6}$$ $$1^2= {6\over 6} = 1$$ Then I use this $$1^2+2^...
3
votes
3answers
250 views

Proof alternating sum of squares is alternating sign of sum

I'm trying to prove by induction that $1-4+9-...\pm n^2 = \pm(1+2+...+n)$. The base-case is obvious, and the formula that I write this as is $$\sum_{i=1}^{n}(-1)^{i+1}i^{2} = (-1)^{n+1}\sum_{i=1}^{...
3
votes
1answer
106 views

Induction over real number

I have to prove a property $P(x)$ hold for $\forall x: x \in (0,1]$. I also have a property $F\big(\frac{x}2\big)=F(x)+1$ which is key to prove $P(x)$. If I prove following steps: $P(x-\epsilon)$ ...
1
vote
1answer
66 views

Why is the enumeration of binary strings misaligned?

If you enumerate the set of binary strings in ascending order, you get: ...
1
vote
2answers
57 views

Induction Proof with Factorials

Problem: If $0 \leq j \leq n-1$, then $(j+1)!(n-j)!\leq n!$. The hint is to use induction and a symmetry argument. Attempt: Base step for induction ($j=0$): $(0+1)!(n-0)! = n! \leq n!$ Induction ...
1
vote
1answer
56 views

Exponents [Discrete Maths]

Had to prove something by induction. Can you please help me by explaining what magic happened after the red $\color{red}=$ in this solution?! $$a_{n+1}=3a_n+4a_{n-1}+6=3(4^n+2(-1)^n-1)+4(4^{n-1}+2(-1)...
0
votes
1answer
65 views

Sum of Harmonic Series

While going through the exercises I found this problem on Induction: Let $$\sum_{i=1}^n\frac{1}{i} = \frac{p}{q}.$$ Prove that $p$ is odd and $q$ is even $\forall\ n\in\Bbb{N}$ and $n \gt 1$. ...
1
vote
4answers
70 views

Prove by induction that $u^{n} - v^{n} > (u - v)^{n}$

I'm having trouble with the following problem: Let u and v be real numbers such that $u > v > 0$ and prove by induction that for all $n \geq 2$, $u^{n} - v^{n} > (u - v)^{n}$. I tried ...
1
vote
2answers
440 views

Induction Sequence on Points on a Circle

Suppose that n a’s and n b’s are distributed around the outside of a circle. Use mathematical induction to prove that for all integers n ≥ 1, given any such arrangement, it is possible to find a ...
1
vote
1answer
43 views

Induction help with final answer

Use induction to prove that for any complex number $z$ that does not equal $1$ and integer n is greater or equal to 1: $$ 1+z+z^2+...+z^n = \frac{1-z^{n+1}}{1-z} $$ So far for the base case I used $z=...
2
votes
4answers
54 views

How does one show that for $k \in \mathbb{Z_+},3\mid2^{2^k} +5$ and $7\mid2^{2^k} + 3, \forall \space k$ odd.

For $k \in \mathbb{Z_+},3\mid2^{2^k} +5$ and $7\mid2^{2^k} + 3, \forall \space k$ odd. Firstly, $k \geq 1$ I can see induction is the best idea: Show for $k=1$: $2^{2^1} + 5 = 9 , 2^{2^1} + 3 = ...