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
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
0answers
46 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
37 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
56 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
59 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
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
31 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
67 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 + ...
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
13 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
68 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 ...
0
votes
3answers
53 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: ...
1
vote
0answers
30 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
41 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
178 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 ...
0
votes
3answers
73 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
53 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 ...
0
votes
1answer
22 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 ...
1
vote
2answers
64 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
39 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
17 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
44 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
45 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
23 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 ...
0
votes
1answer
26 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
41 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 ...
1
vote
1answer
27 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 ...
0
votes
1answer
19 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
55 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
30 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: ...
0
votes
0answers
37 views

Induction: finding a formula equal to the one given [closed]

so i needed help Determining the formual for $\sum_{k=1}^n (2k-1)$ I understand now. Thankyou every one for your time and help!
0
votes
2answers
95 views

Give a formal proof by induction that $f^k(m, n) = (m − kn, n)$ for all $k\in\Bbb Z^+$.

i understand in general how an induction proof works, however I'm having difficulties with the following question: Let $f :\Bbb Z^2 \to\Bbb Z^2$ be given by $f(m, n) = (m − n, n)$. The composite ...
3
votes
0answers
32 views

Historical use of k in proof by induction

Does anybody know the history of why the symbol k is used in proof by induction? As an example, in physics the symbol p is used for momentum because Newton called it impetus, and the letters i and m ...
0
votes
2answers
24 views

Show $∀n≥3$, $2n^2+1 ≥ 5n$

I was able to prove the base case statement, where if you plug in $3$ for $n$ you get: $19 ≥ 15$. Next I supposed an arbitrary value $k$ where $k ≥ 3$ and $2k^2+1 ≥ 5k$. I know that next I need to ...
-2
votes
5answers
41 views

Prove by induction that for every $n \in \mathbb{N}$, $(1 + \sqrt{3})^n + (1 - \sqrt{3})^n \in \mathbb{Z}$. [closed]

Prove by induction that for every $n \in \mathbb{N}$, $(1 + \sqrt{3})^n + (1 - \sqrt{3})^n \in \mathbb{Z}$.
2
votes
3answers
52 views

Prove that $n^4-n^2$ is divisible by $8$ if $n$ is an odd positive integer.

Prove that $n^4-n^2$ is divisible by $8$ if $n$ is an odd positive integer. I'm supposed to use proof by induction, but I failed at it miserably. So far I have this: $$(n^4) - (n^2) = ...
0
votes
0answers
30 views

How to induct for double summation?

I have no idea on how to approach this? $$ \sum_{i=1}^{n}\sum_{j=1}^{m}a_i + a_j = \sum_{i=1}^{n} a_i + \sum_{i=1}^{m} a_j (it \space may \space be \space wrong \space it \space is \space just ...
0
votes
3answers
63 views

Prove by induction that the Fibonacci sequence $≤ [(1+\sqrt{5})/2]^{n−1}$, for all $n ≥ 0$.

If $F(n)$ is the Fibonacci Sequence, defined in the following way: $$ F(0)=0 \\ F(1)=1 \\ F(n)=F(n-1)+F(n-2) $$ I need to prove the following by induction: $$F(n) \leq ...
0
votes
1answer
26 views

Find a recurrence for the number of ways to arrange cars in a row with $n$ parking spaces

Find a recurrence for the number of ways to arrange cars in a row with $n$ parking spaces if we can use Cadillacs or Hummers or Fords. A Hummer requires two spaces, while a Cadillac or Ford requires ...
0
votes
3answers
38 views

Induction mathematics

Assume $a_1 = 4$ and $a_{n+1} = \sqrt{3+2a_n}$ for all integers $n ≥ 1$. Show with induction that $\forall n ≥ 1, \space a_n > a_{n+1} > 3$. Help me solve this please
2
votes
1answer
21 views

Sum of reciprocals of squares - bounding

Recently in class our teacher told us about the evaluating of the sum of reciprocals of squares, that is $\sum_{n=1}^{\infty}\frac{1}{n^2}$. We began with proving that ...
1
vote
5answers
85 views

Proving that $8^n - 3^n$ is divisible by $5$

I really should be able to do this but I don't know why I can't figure it out. My problem is that I have to prove $8^n - 3^n$ is divisible by $5$. So what I did is I tried it for $n=1, n=2, n=3$ and ...
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 + ...
7
votes
1answer
104 views

$2005$th derivative of $f$ at $0$

So I tried using Leibnitz formula to solve by recurrence, but I can just get to one point and then it's a mess again. Problem is Let $f(x)=\frac{1}{1+2x+3x^2+\ldots+2005x^{2004}}$. Find ...