Induction in general is the inference from the particular to the general. Mathematical induction is not true induction, but is a form of deductive reasoning. Its most common use is induction over well ordered sets, such as natural numbers, or ordinals. While induction can be expanded to class ...
4
votes
2answers
82 views
Demonstrate by induction the inequality: $\ln(1+n)\leq\sum_{i=1}^{n}\frac{1}{i}\leq1+\ln(n)$
Kind of stuck in this one. I've tried substracting
$$\ln(1+(n+1))\leq\sum_{i=1}^{n}\frac{1}{i}+\frac{1}{n+1}\leq1+\ln(n+1)$$
at the original inequality and applying properties of the logarithms, but ...
0
votes
0answers
51 views
proving an inequality by induction
Not sure how to proceed. I'm trying to prove that the following inequality is true. I know that $t_2 = 6$ and $t_3=17$ from the problem statement. The base case is obvious.
$t_{r+1} \leq (r+1) (t_r ...
5
votes
1answer
60 views
Proving the following inequality using induction?
I need to prove by induction that $Q_n \ge\frac{10}{3}-\frac5{3n}$ for $n\ge2$$$
Q_n = ...
0
votes
3answers
53 views
Proving the formula is correct by induction
$$P_n = \prod^n_{k=2} \left(\frac{k^2 - 1}{k^2}\right)$$ Someone already helped me see that $$P_n = \frac{1}{2}.\frac{n + 1}{n} $$ Now I have to prove, by induction, that the formula for $P_n$ is ...
3
votes
1answer
32 views
Formula for this sequence?
$P_n= \prod^n_k_=_2 \frac{k^2-1}{k^2}$ for $n \ge 2$
I calculated $P_1 to P_3$ . I have been trying to come up with a formula but I can't really see any pattern.
$P_2 = \frac{3}{4} , P_3 = ...
1
vote
1answer
56 views
Prove by Induction $\frac{a_n-\sqrt{A}}{a_n+\sqrt{A}} = \left[\frac{a_1-\sqrt{A}}{a_1+\sqrt{A}}\right]^{2^{n-1}} $
$a_1=\frac{1}{2}(a_0+\frac{A}{a_0})$;
$a_2=\frac{1}{2}(a_1+\frac{A}{a_1})$; and
$a_{n+1}=\frac{1}{2}(a_n+\frac{A}{a_n})$ for $n \geq 2$; where $a\gt 0$, $A\gt 0$.
Prove:
...
3
votes
3answers
56 views
The number of positive integers which are less than $mk$ and coprime to $m$ is $k\phi(m)$.
Let $m,k$ be positive integers. Then the number of positive integers $\leq mk$ prime to $m$ is $k\phi(m)$.
My approach would be to use induction on $k$. If $k=1$, then by definition the result ...
3
votes
4answers
59 views
How to prove $\sum^n_{i=1} \frac{1}{i(i+1)} = \frac{n}{n+1}$? [duplicate]
How can I prove that $\sum^n_{i=1} \frac{1}{i(i+1)} = \frac{n}{n+1}$? I noticed that in the sum, the denominator has terms that cancel out, but I'm not sure how to take advantage of that.
3
votes
4answers
78 views
Proof by induction help. I seem to be stuck and my algebra is a little rusty
Stuck on a homework question with mathematical induction, I just need some help factoring and am getting stuck.
$\displaystyle \sum_{1 \le j \le n} j^3 = \left[\frac{k(k+1)}{2}\right]^2$
The ...
5
votes
3answers
522 views
Complete induction
I am very confused with complete induction. Because in every task there is something different to do, and I never know what to insert (thats my biggest problem).
Here's the example:
Proof with ...
1
vote
1answer
86 views
Proving the Existence of Triangle by Induction
There is an exercise which is should be proven by induction:
$2n$ points are given in space. Altogether $n^2+1$ line segments are
drawn between these points. Show that there is at least one set ...
7
votes
1answer
119 views
An inequality using mathematical induction
It was shown in here that $\left(1+\frac{1}{n}\right)^n < n$ for $n>3$. I think we can be come up with a better bound, as follows:
$$\left(1+\frac{1}{n}\right)^n \le 3-\frac{1}{n}$$
for ...
1
vote
2answers
54 views
Non-induction proof of $2\sqrt{n+1}-2<\sum_{k=1}^{n}{\frac{1}{\sqrt{k}}}<2\sqrt{n}-1$
Prove that $$2\sqrt{n+1}-2<\sum_{k=1}^{n}{\frac{1}{\sqrt{k}}}<2\sqrt{n}-1.$$
After playing around with the sum, I couldn't get anywhere so I proved inequalities by induction. I'm however ...
1
vote
1answer
73 views
Mathematical Induction problem- how to show that $P(\bigcup_{i=1}^nA_i)\leq\sum_{i=1}^n P(A_i)$?
Hi I tried doing this problem but im not sure if I am correct can someone help
So this what I did
Now I am not so sure if this is right
2
votes
1answer
144 views
Concrete Mathematics - The Josephus Problem
I've been going through Concrete Mathematics and have a question on the inductive proof for the Josephus problem.
Recurrent relation:
$J(1) = 1$
$J(2n) = 2J(n) - 1$
$J(2n+1) = 2J(n) + ...
2
votes
3answers
96 views
Proof that a n-hypercube is n-vertex-connected
I'm new to graph theory, I'm finding it hard to get upon proofs.
To prove: An n-hypercube is n-vertex connected. Approaches I thought:
It holds true for n=2, so ...
0
votes
0answers
82 views
Strong induction implies weak induction
I know how weak induction implies strong induction
ie. proving strong induction with weak induction
Let Q(n) be P(1) ∨ P(2) ∨...∨ P(n)
Base case: Q(1) = P(1) by definition
Inductive step:
Q(k) -> ...
1
vote
1answer
70 views
Equivalence of strong and weak induction
What is a simple way of proving strong induction implies weak induction and vice versa using simple predicate logic and quantifiers?
1
vote
2answers
144 views
Basic proof by Mathematical Induction
I am new to proofs and I am trying to learn mathematical induction. I started working out a sample problem, but I am not sure if I am on the right track. I was wondering if someone would be kind ...
4
votes
4answers
124 views
Prove by Mathematical Induction: $1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!) = (n+1)!-1$
Prove by Mathematical Induction . . .
$1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!) = (n+1)!-1$
I tried solving it, but I got stuck near the end . . .
a. Basis Step:
$(1)(1!) = (1+1)!-1$
$1 = ...
2
votes
3answers
63 views
Induction: prove using congruences
Prove that:
$$a^{2^n} \equiv 1\pmod{2^{n+2}}$$
I have done the base case, and then have an assumption that:
$$a^{2^k} \equiv 1 \pmod {2^{k+2}}$$
I wish to prove the last step, that:
$$a^{2^{k+1}} ...
3
votes
2answers
59 views
Proving the size of the unions of sets
How should one go about proving the following with induction?
$$ \left| \bigcup_{i \in I} A_i \right| = \sum_{J \subseteq I} (-1)^{|J|+1} \left|\bigcap_{i \in J} A_i \right| $$
I is just a finite ...
2
votes
4answers
182 views
Fibonacci Induction Proof
Using induction, how can I show the following identity about the fibonacci numbers? I'm having trouble with simplification when doing the induction step.
Identity: $$f_n^2 + f_{n+1}^2 = f_{2n+1}$$
I ...
0
votes
2answers
32 views
How to present this inductive proof more clearly
Not sure where to go with this
$2^k > k^3$ for $k > 9$
$2^(k+1) > (k+1)^3$
$2^(k+1) = 2^k \cdot 2$
$2^k \cdot 2 > k^3 \cdot 2$ (by inductive hypothesis)
$2^k \cdot 2 > 2k^3$
$2k^3 ...
1
vote
3answers
58 views
What numbers can be written as a sum of two or more consecutive odd numbers?
I'm having trouble setting up a case and proving through induction or whether there is a better way to prove this.
2
votes
2answers
148 views
Induction Proof: $\sum_{i=1}^{n+1} i \cdot 2^i = n \cdot 2^{n+2}+2 $
Prove by Mathematical Induction . . .
$$\sum_{i=1}^{n+1} i \cdot 2^i = n \cdot 2^{n+2}+2 $$
for all $n \geq 0$
I tried solving it, but I got stuck near the end . . .
a. Basis Step:
$1\cdot 2^1 ...
0
votes
2answers
76 views
Linear algebra identity proof by induction
I want to prove that $\begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}^n=\begin{pmatrix}1 & n\\ 0 & 1\end{pmatrix}, n=1,2,3\dots$
by induction, I've come this far:
Basis:
...
2
votes
2answers
56 views
How to prove that $+$ is commutative on the natural numbers?
Let $N$ be a non empty set. Let $s:N\to N$ a function satisfying:
there is only one element in $N-s(N)$ (denoted by $1$);
$s$ is injective;
for any subset $X\subset N$, if $1\in X$ and $(n\in N ...
0
votes
1answer
64 views
Solving problem about disjunction, conjunction, implication, and equivalence, by induction
How to solve with induction?
For all finite sets $I \neq \emptyset$.
$ \left( \bigvee_{i \in I} P_i \right) \Rightarrow Q \equiv \bigwedge_{i \in I} (P_i \Rightarrow Q)$
2
votes
3answers
116 views
Something kind of like proving the euclidean Algorithm by induction
Let a > b be positive integers. In applying the Euclidean algorithm,
we have $a = b q_0$ + $r_0$, $b = r_0 q_1 + r_1$, and $r_{n-1} = r_n q_{n+1} + r_{n+1}$, for all $n > 0$. Prove by induction ...
1
vote
1answer
49 views
Prove $n!>2^n$ for $n\geq4$ using induction. [duplicate]
I just want to know if my proof to this question is correct. First, I proved it was true for $n = 4$. $$4!>2^4$$ $$24>16$$ Then, I assumed that it was true for $n=k$. $$k!>2^k$$ Afterwards, I ...
6
votes
4answers
122 views
Proving ${(n+2)!}< \left(n(\sqrt{2}-1)+\sqrt{2}\right)^{n+2}$
While simplifying an inequality, this inequality was derived:
$${(n+2)!}< \left(n(\sqrt{2}-1)+\sqrt{2}\right)^{n+2},\quad\quad\quad\quad n\in \mathbb{N}$$
Do you have any idea to prove it? It is ...
1
vote
3answers
70 views
inductive prove$\sum_{k=1}^{n} \binom n k = 2^n -1 $
today i wrote calculus exam, i had this problem given, which was to prove by induction: $$\sum_{k=1}^{n} \binom n k = 2^n -1 $$ for all $n\in \mathbb{N}$
i have the feeling that i will get $0$ points ...
4
votes
0answers
115 views
Efficiently count possible nim-like moves
Consider $n$ piles of coins, with pile $i$ having $a_i$ coins. A valid move is to remove zero or more coins from each of the piles, with the constraint that atleast one pile should remain unchanged, ...
0
votes
2answers
62 views
Help with math induction $S_{n+1}=1+aS_n$
Using mathematical induction I would like to prove the following.
$S_0=1$
$S_1=1+a,...,S_n=\sum_{i=0}^n a^i$
Prove that $S_{n+1}=1+aS_n$ where $n \ge 0$.
2
votes
5answers
110 views
Induction on binomial Identity
I am having trouble proving the following identity:
$0\cdot {n\choose 0} + 2\cdot {n\choose 2} + 4\cdot {n\choose4}+\ldots = n\cdot2^{n-2}$
Here is what I have so far:
Proof:
Base: Let $n=0$:
...
7
votes
3answers
235 views
Looking for induction problems that are not formula-based
I am looking for problems that use induction in their proofs such as this one: Given a checker board with one square removed you can cover it with L-shaped pieces made out of three squares. This ...
4
votes
4answers
120 views
Prove that $1^3 + 2^3 + … + n^3 = (1+ 2 + … + n)^2$
This is what I've been able to do:
Base case: $n = 1$
$L.H.S: 1^3 = 1$
$R.H.S: (1)^2 = 1$
Therefore it's true for $n = 1$.
I.H.: Assume that, for some $k \in \Bbb N$, $1^3 + 2^3 + ... + k^3 = (1 ...
2
votes
2answers
89 views
How to prove this with induction
$$(P_0 \lor P_1 \lor P_2\lor\ldots\lor P_n) \rightarrow Q $$
is the same as
$$(P_0 \rightarrow Q) \land (P_1 \rightarrow Q) \land (P_2 \rightarrow Q) \land\ldots\land(P_n \rightarrow Q)$$
Do I ...
3
votes
2answers
117 views
Prove by Induction
For $n\in \mathbb{N}$ and $z\in \mathbb{C}$:
$\sin{(nz)}=\sum _{ k=0 }^{ n }{ \binom{n}{k} }\frac{1}{2i}(i^k-(-i)^k)(\cos{z})^{n-k}(\sin{z})^k $
$\cos{(nz)}=\sum _{ k=0 }^{ n }{ ...
0
votes
2answers
51 views
1
vote
1answer
37 views
Sets induction problem
Let $n\ge 2$ and $A_1,\dots,A_n$ be sets in some universe $S$. In this problem we will give a proof by induction of the identity $$\left(\bigcap_{i=1}^nA_i\right)^c=\bigcup_{i=1}^nA_i^c\;.$$
...
1
vote
1answer
139 views
Proving the sum of the first n natural numbers by induction
I have the Following Proof By Induction Question:
$$ (1)(2) + (2)(3) + (3)(4) + \cdots+ (n) (n+1) = \frac{(n)(n+1)(n+2)}{3} $$
Can Anybody Tell Me What I'm Missing.
This is where I've Gone So Far.
...
3
votes
4answers
189 views
Proving the sum of the first $n$ natural numbers by induction
I am currently studying proving by induction but I am faced with a problem.
I need to solve by induction the following question.
$$1+2+3+\ldots+n=\frac{1}{2}n(n+1)$$
for all $n > 1$.
Any ...
0
votes
2answers
255 views
Factorial (Proof by Induction)
Prove by induction that $n!<n^n$ for all $n>1$.
So far I have (using weak induction):
Base Case: Proved that claim holds for $n=2$
Induction hypothesis: For some arbitrary $n>1, n!<n^n$
...
2
votes
2answers
90 views
$9^n \equiv 1 \mod 8$
I would like someone to check this inductive proof (sketch)
The base case is clear. For the inductive step, it follows that $8 \mid 9^{n+1} - 9 = 9(9^n - 1)$ by the indutive hyp. So $9^{n+1} \equiv ...
0
votes
1answer
38 views
How can I prove a sequence of values follows a certain closed form equation?
For example, imagine I'm trying to do this
$$
(1-3x+3x^2)/(1-3x+3x^2-3x^6) = \sum\limits_{n=0}(a_nx^n)
$$
$$
(1-3x+3x^2) = \sum(a_nx^n) * (1-3x+3x^2-3x^6)
$$
Then say we are given some closed ...
1
vote
2answers
84 views
Proof by induction that $f^{(n)}(x)=p_n(x)e^{x^2}$ where $f(x)=e^{x^2}$
Let $f(x)=e^{x^2}$. Show by induction that $f^{(n)}(x)=p_n(x)e^{x^2}$ where $p_n(x)$ is an $n$th degree polynomial. $f^{(n)}(x)$ is the $n$th derivative of $f(x)$.
Tip: You do not need to find a ...
0
votes
3answers
40 views
Prove $\sum_{i=0}^{n} a^i = \frac{a^{n+1} - 1}{a - 1}$ by induction
I was assigned two induction problems that I tried to solve. One was easy to solve using the following method, but one got me stuck. Problem:
Prove by induction on $n \geq 1$ that for every $a ...
1
vote
0answers
142 views
Why Does Induction Prove Multiplication is Commutative?
Andrew Boucher's General Arithmetic (GA2) is a weak sub-theory of second order Peano Axioms (PA2).
GA has second order induction and a single successor axiom:
$$\forall x \forall y \forall ...
