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

3
votes
5answers
113 views

7 Cents and 11 cents Stamps Mathematical Induction

Assume you can only use 7-cent and 11-cent stamps. a) Determine which amounts of postage can be formed by the given stamps. b) Prove your answer using the principle of mathematical induction. c) ...
2
votes
3answers
67 views

Proof using induction n!

I wanna know how to proof using induction; I saw this example in a discrete book; however, i could not solve it; the question is below: Prove, using induction, that $3^{n} < n!$ for all $n ≥ 7$
2
votes
1answer
56 views

Is the sequence a graphic sequence?

Let $S=\{a_1,a_2,\dots,a_n\}$ be a set of distinct integers. Let $k$ is the least common multiple of the numbers $\{a_1+1,\dots,a_n+1\}$. Prove that the sequence that is take all the elements of $S$ ...
0
votes
4answers
52 views

Induction proof: $n^2+3n$ is even for every integer

Prove using simple induction that $n^2+3n$ is even for each integer $n\ge 1$ I have made $P(n)=n^2+3n$ as the equation. Checked for $n=1$ and got $P(1)=4$, so it proves that $P(1)$ is even. ...
0
votes
0answers
18 views

Solving recurrence relation $T(n)\le T(0.9n)+T(0.2n)+O(n)$

I'm trying to solve the following recurrence relation $$T(n)\le T\left(\frac{9}{10}n\right)+T\left(\frac{1}{5}n\right)+\text{O}(n)$$ According to book it should be that $T(n)=\text{O}(n^2)$. I ...
2
votes
1answer
49 views

Valid Induction Argument involving Closed Form for $\Gamma(1/2-n)$

Given $\Gamma\left(\frac1{2}\right)=\sqrt{\pi}$, $$\sqrt{\pi}=\Gamma\left(\frac1{2}\right)=\Gamma\left(-\frac1{2}+1\right)=-\frac{1}{2}\Gamma\left(-\frac1{2}\right)$$ and so ...
2
votes
1answer
49 views

Proof of a Four-Pole Tower of Hanoi

Four-Pole Tower of Hanoi: Suppose that the Tower of Hanoi problem has four poles in a row instead of three. Disks can be transferred one by one from one pole to any other pole, but at no time may a ...
3
votes
1answer
79 views

Proof with induction for a Tower of Hanoi with Adjacency Requirement

Tower of Hanoi with Adjacency Requirement: Suppose that in addition to the requirement that they never move a larger disk on top of a smaller one, the person who move the disks of the Tower of Hanoi ...
1
vote
3answers
88 views

Divisibility by 4 (induction proof)

We have to show that $$ n^4 -n^2 $$ is divisible by 3 and 4 by mathematical induction Proving the first case is easy however I do not know how what to do in the inductive step. Thank you.
1
vote
0answers
53 views

Induction in the Reals?

In most maths textbooks, proofs by induction prove a statement $P_n$ where $n$ usually is in the natural numbers (although I understand that it can be in any discrete collection as long as you prove ...
-1
votes
1answer
58 views

Mathematical Induction in constructive setting [closed]

I'm little confused. As we don't have a proof hence we can't say : let the equation holds till(for) fixed n, and then we are going to show (prove) it holds for n + 1. From this argument mathematical ...
1
vote
2answers
49 views

Im having trouble with a proof by induction

the question is: let $$a_{n} = 1$$ and $$a_{n+1}=\frac{a_{n}}{1+(n+1)a_{n}}$$ for each natural number n. prove by induction that $$a_{n} = \frac{2}{n(n+1)}$$ for every natural number. and deduce that ...
1
vote
1answer
26 views

Prove that every permutation in $S_k$ is the product of transpositions of the form $(j, j + 1).$

Prove that every permutation in $S_k$ is the product of transpositions of the form $(j, j + 1).$ I proved the case $n=2$ for my base case... so $(12)=(21)$ and $(21)=(12)(12)$ then I proved $n=3$ and ...
1
vote
1answer
40 views

Show that $H_{2^n}$ $\leq$ $1+n$ with induction

Use mathematical induction to show that $H_{2^n}$ $\leq$ $1+n$, whenever n is a nonnegative integer. PS: $H_{2^n}$ denotes the $2^n$th harmonic number.
2
votes
1answer
54 views

Prove Dirac's Theorem by induction on the number of vertices

Dirac's Theorem says: If a connected graph $G$ has $n \ge 3$ vertices and $\delta(G) \ge \frac{n}{2}$, then $G$ is Hamiltonian. Now I want to prove this theorem by induction on $n$. For ...
0
votes
1answer
31 views

Induction Validity

Is it valid in an induction to prove a base case for$ n=3$then prove for $n=4$ and use the fact that the transition from $n=3$ to $ 4$ was possible to then prove it is possible for $n=k$ and $ n=k+1?$ ...
0
votes
1answer
32 views

Misere nim, 2nd player winning strategy proof by induction

I'm having a problem with writing on paper things that I came up with. There's a Misere nim game with n stones, two players, every player can take 1, 2, 3 or 4 stones in one round, the one to remove ...
0
votes
1answer
26 views

How do I start the inductive step in strong induction proof?

Define a sequence as follows: $a_1 = 1$, $a_2 = 3$ and $a_{n+1} = a_{n-1} + a_n$ for integers $ n \ge 2$ Use strong induction to prove that for all integers $n\ge1$, we have $a_n \lt ...
1
vote
1answer
39 views

$\{a_n\}$ is a sequence of real numbers defined by $a_1=1$, $a_2=2$, $a_3=3$ and $a_n=2a_{n-1} - a_{n-3}$

Image of problem: http://d2vlcm61l7u1fs.cloudfront.net/media%2F901%2F9010d0fd-aeea-43bb-a993-9327afc7df9e%2FphpiKWhi5.png Text of problem: $\{a_n\}$ is a sequence of real numbers defined by $a_1=1$, ...
1
vote
2answers
66 views

How do I start the inductive step?

Let $x$ be any real number greater than -1. Prove that $(1 + x)^n\;\ge\;1+nx$ for every $n\ge0$ by induction. The basis step is easy. I am struggling with starting the inductive step. Can you give me ...
0
votes
7answers
176 views

Is there any proposition provable by induction whose evaluation oscillates for small numbers and is true for all large enough numbers?

Actually, I want a proposition $P(n)$ defined over the natural numbers such that: $P(a)$ is true. $P(b)$ is false. $P(c)$ is true. $a<b<c$. $P(n)$ is true for all $n \geq n_0$. We can prove ...
4
votes
2answers
58 views

Prove that for $n\ge 2$, $2{n \choose 2}+{n \choose 1} = n^2$

I'm new to this website, so I don't really know the MathJax equations, but I do need some help on this proof. I would assume that we can prove by induction. Base case $n=2$. $$=2{2 \choose 2}+ {2 ...
5
votes
2answers
49 views

N points contained in circle with radius 1

Consider a set of $n$ points in the plane such that any three of them are contained in a circle with radius $r=1$. Prove by induction that all $n$ points are contained in a circle with radius $r=1$.
0
votes
2answers
30 views

L-shaped trominoes

Use Math Induction to prove that any checkerboard with dimensions 2 x 3n can be completely covered by L-shaped trominoes for any integer n $\ge$ 1. How do I go about proving a problem like this? I ...
3
votes
2answers
31 views

Proving $\sum_{i=1}^n i(i!) = (n+1)! -1$ by Mathematical Induction

Theorem: For any integer n $\ge$ 1. $$\sum_{i=1}^n i(i!) = (n+1)! -1$$ Prove by mathematical induction. I have this problem and I know how to go about it, but I don't understand what I should do ...
0
votes
0answers
29 views

Proving a family of polynomials is linearly independent

I am attempting to solve the following problem, but I'm confused on a solution that is offered for it. The question asks "Let $S$ $=$ {$P_1,..., P_n$} be a family of polynomials such that for all ...
0
votes
1answer
19 views

Is this a valid base case?

I'm trying to prove this for all $n \geq 1$. Using the recursive formula, I ended up with this: $F_{-(n+1)} = F_{-n} - F_{-(n+2)}$. If the formula holds for $n$ and $n+2$, I can eventually turn the ...
0
votes
3answers
44 views

$x-y$ divides $x^n - y^n$ — prove by mathematical induction [closed]

I'm doing some prove by mathematical induction practice problems. I got to this last problem but I don't know how to approach it. This is the question For all positive integers $n$ and any distinct ...
1
vote
1answer
82 views

Proof using strong induction a conjecture about $4^n$

Compute $4^1$, $4^2$, $4^3$, $4^4$, $4^5$, $4^6$, $4^7$, and $4^8$. Make a conjecture about the units digit of $4^n$ where $n$ is a positive integer. Use strong mathematical induction to prove your ...
0
votes
1answer
41 views

Mathematical induction for particular formula.

I'm currently learning mathematical induction, but I'm not sure how to start a proof for this formula(the problem is different than what I've been practicing with). I'm not looking for the whole ...
2
votes
0answers
40 views

Binomial Theorem Proof by Induction

Did i prove the Binomial Theorem correctly? I got a feeling I did, but need another set of eyes to look over my work. Not really much of a question, sorry.
0
votes
1answer
19 views

iterate algorithm/program correctness proof by induction

Suppose I have a function where it calculates which bit is larger called LargerBinary. Let's say I have an input 110111;101001, the output will be 110111 and if the input is 110110:110110, the output ...
4
votes
2answers
50 views

Proving $3^n \geq 3n$ using mathematical induction

So I have to prove that $3^n$ is greater than or equal to $3n$ using induction. The base case is a not a problem, but I can't seem to figure out where to go for $(n-1)$. I've tried saying: ...
1
vote
2answers
60 views

Prove that $7 | (3^{2n + 1} + 2^{n +2})$

Prove that $7 | (3^{2n + 1} + 2^{n +2})$ So far I have: Base case: n = 1 $ = (3^{2(1) + 1} + 2^{(1) +2})$ $ = (3^{3} + 2^{3})$ $ = (35)$ which divides 7 Inductive Step: $ = (3^{2(n +1) + 1} + ...
5
votes
2answers
72 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$ ...
3
votes
0answers
45 views

proof - any positive integer can be uniquely expressed as $a = 3^m + 3^{m-1}b_{m-1} + \cdots + 3^0b^0$ [duplicate]

I had been trying to prove that any positive integer can be uniquely expressed as $$a = 3^m + 3^{m-1}b_{m-1} + \cdots + 3^0b^0 \text{ where each b = -1, 0 or 1 and } a \in \mathbb{Z}^+$$ This is a ...
1
vote
1answer
37 views

Prove by induction - can not prove the step case

I have to prove by induction the following: $$\sum^{n-1}_{k=2} k\log_{10} k \le \frac{1}{2}n^2\log_{10} n-\frac{1}{8}n^2$$ I have proven the base case, but I am stuck at the step case. I have tried ...
2
votes
2answers
28 views

Using induction, prove for every $n \in \mathbb{N}$, there exists number of $n$ digits $M_n$ = $a_1$, $a_2$,… $a_n$, …$2^n$ divides $M_n$

Using induction, prove for every $n \in \mathbb {N}$, there exist a number of $n$ digits $M_n$ = $a_1$, $a_2$,... $a_n$ with $a_i \in \{2,3\}$ such that $2^n$ divides $M_n$. I understand how ...
0
votes
2answers
46 views

Induction proof: $\sum_{k=1}^n k^32^k \leq n^32^{n+1}$

Having trouble solving the induction proof for: $$\sum_{k=1}^n k^32^k \leq n^32^{n+1}$$ EDIT: supposed to be $k^32^k$
0
votes
1answer
37 views

Does $a_n$ increasing imply $a_n-\frac{1}{n}$ strictly increasing?

Let $(a_n)_{n=1}^\infty$ be a sequence in $\mathbb{R}$. If $(a_n)$ is increasing prove that $(a_n-1/n)$ is strictly increasing. How can I start off this off this question via induction?
2
votes
3answers
35 views

Deductive proof in natural numbers - division

Prove, using induction rule: $$\forall_{n\in N} \left (2^{2n+1} + 3n + 7 = 9c\right)$$ $$c\in N$$ 1. I checked with 1 : works 2. I assumed that it is true for some natural number k 3. I plugged in ...
2
votes
3answers
55 views

Why is it okay to write…“for $n\in\mathbb{Z}^+,n\ge 3.5$”?

So I've been playing around with some mathematical induction proofs and I usually open with a statement similar to: (example below) Denote the statement involving $n$ for $n\in\mathbb{Z}^+,n\ge 4$ ...
1
vote
1answer
57 views

Proof with induction on a sequence

Let $\{a_k\}_{k=0}^\infty$ be a sequence where $a_0 = 0$ $a_1 = 0$ $a_2 = 2$ $\forall k \geq 3, a_k = a_{\lfloor k/2 \rfloor} + 2$ Show that every element of this sequence is even. I am ...
-7
votes
1answer
69 views

Using Induction to prove a sequence [closed]

How do i prove that $a_{n+1}$ is even? I have tried many things but can't seem to get anywhere in turns of proving. Define the sequence $(a_n)$ as follows $a_0 = 0$, $a_1 = 0$, $a_2 = 2$, $a_n = ...
1
vote
2answers
38 views

Induction Proof $k^2 \times 2^k$

I need help on this proof. I am not able to do it after setting m=m+1. Prove by induction on n that sum of $k^2 \times 2^k$ from $k=1$ to $n$ is equal to $(n^2-2n+3) \times 2^{n+1}-6$ Base case: ...
1
vote
1answer
27 views

From finite union to infinite union

Given a possibly infinite set $S$ which is closed under the union of two members, ie $x,y\in S\implies x\cup y\in S$, how can I show $S$ is closed under the union of all elements, ie $\bigcup S\in S$? ...
0
votes
0answers
9 views

How to show by induction that for $f(t) = \sum_{j=0}^k a_j t^j$ we have $\Delta^k f(t) = k!a_k$?

I am asked to prove by induction that for $f(t) = \sum_{j=0}^k a_j t^j$ we have that $\Delta^k f(t) = k!a_k$. For those who do not already know $\Delta$ is the backward difference operator, i.e., ...
1
vote
1answer
49 views

Efficient way to show Graph is a tree in proof

I am new to inductive proofs in general, and brand new to graph proofs. I am looking for an efficient way to declare that the induced subgraph prior to application of induction is, in fact, a tree. ...
4
votes
1answer
61 views

Proof Fibonacci derivation

I was wondering how to prove that $$f(n+m+2) = f(n+1)f(m+1) + f(n)f(m)$$ where $f$ is the fibonacci sequence and n, m are positive integers. Can be this done with induction? I'm lost with this ...
1
vote
1answer
65 views

Product matrix and induction

I am not sure which method to use here. Should I do it for $n=2$ and $n=3$ and then use induction on $n$? Let $\alpha_1,\alpha_2,\ldots,\alpha_n \in \mathbb{R}$, where $n \geq 2$. Show that ...