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 ...

learn more… | top users | synonyms

1
vote
2answers
42 views

Prove by mathematical induction that exponentials grow faster than polynomials

How to prove that for $\forall q>1$ $\forall k\in \mathbb{N}$ $\exists c>0$ $\forall \in \mathbb{N}$ $q^n≥cn^k$? I should use mathematical induction.
0
votes
2answers
18 views

Combinatorics identity proof by induction

Prove the formula by induction on n and fixed r: $\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \ldots + \binom{n}{r} = \binom{n+1}{r+1}$ What I tried: Base: we take $n=r$ so $\binom{r}{r} = ...
1
vote
2answers
28 views

Inductive proof of the degree of a polynomial

Here is the problem: Assume that there is a polynomial $P(x)$ of degree 4 such that for all $N \in \mathbb{N}$, $$P(N) = \sum\limits_{n=0}^N n^3$$ Find the polynomial. Use induction to prove that ...
7
votes
2answers
57 views

Function composition: $f^{653}(56)=?$

Let $f(x) = \frac1{(1-x)}$. Define the function $f^r$ to be $f^r(x) = f(f(f(...f(f(x)))))$. Find $f^{653}(56)$. What I've done: I started with r=1,2,3 and noticed the following pattern: $$f^r(x)= ...
2
votes
2answers
30 views

Prove By Induction (Fibonacci Sequence)

Prove by PMI $\gcd(f_n,f_{n+1}) = 1$ for all natural numbers $n$. $f_n$ represents the Fibonacci sequence.
1
vote
2answers
36 views

Number of particles at time $t$

A following problem appears in my text book under the section of induction: At time $0$, a particle resides at the point $0$ on the real line. Within $1$ second, it divides into $2$ particles that ...
1
vote
1answer
38 views

prove weak induction implies strong induction

There is a solution from a year ago that I don't quite follow which is why I post this along with my attempt, so it is not a duplicate. Prove weak induction implies strong induction: weak ind. ...
1
vote
0answers
20 views

Game of writing a binary sequence proof

Let $n \gt 2$ be a natural number. We consider the following game. Two players write a sequence of $0$s and $1$s. They start with an empty line and alternate their moves. In each move, a player writes ...
0
votes
1answer
63 views

Using induction for $x^n - 1$ is divisible by $x - 1$

Prove using induction that for all non-negative integers n and for all integers $ x > 1 $, $ x^n - 1 $ is divisible by $ x - 1 $. Step 1: We will prove this using induction on n. Step 2: Assume ...
1
vote
2answers
28 views

Induction on the number of marbles in a heap.

Here is the problem in full: "A heap has $x$ marbles, where $x$ is a positive integer. The following process is repeated until the heap is broken down into single marbles: choose a heap with more ...
0
votes
3answers
32 views

Proof by Induction: Series of binomial coefficients with same k-length subsets

I have no idea how to prove this binomial equation identity. For reference this is included in Discrete Mathematics for Computer Scientists by Clifford Stein, Robert Drysdale and Kenneth Boggart, ...
0
votes
1answer
34 views

Inductive proof on r

Let $r, n ∈ N$ and let $r ≤ n$. Give an inductive proof for: $$ {n+1 \choose r + 1} = ∑_{k=r}^n {k \choose r} $$ Step 1: We will prove this using induction on n. n = 1 Step 2: n = k, prove for n = ...
0
votes
1answer
21 views

Proof by induction with two variables

Giving proof by induction is normally very straight forward: $n+1$ and such. But how do you deal with two variables $m$ and $n$? Given this problem, how do I ensure that I'm proving for $n+1$ and ...
0
votes
1answer
38 views

Induction proof divisible by 5

Prove that for all n ∈ N, prove that $ 3^{3n+1} + 2^{n+1} $ is divisible by 5. So far what I've gotten is: Step 1: We will prove this by using induction on n. Assume the claim is true when n = k. ...
0
votes
0answers
39 views

Favourite proofs by induction?

I am searching for nice proofs by induction, that can be used to teach. I remember this example, that my analysis professor presented to us in first semester and I am searching for more such easily ...
2
votes
5answers
53 views

Prove that $e^x \ge$ its Maclaurin polynomial with n terms [on hold]

a) show that $e^x \geq 1+x$ for all $x\geq 0$ b) deduce that $e^x \geq 1+x+\frac{1}{2}x^2$ for $x\geq0$ c) use induction to prove that for $x\geq 0, n\in \mathbb{N}$ $$e^x\ge ...
-1
votes
0answers
35 views

Proof of big theta using induction [on hold]

Here is a recursive definition for the runtime of some unspecified function. $a$ and $c$ are positive constants. $T(n) = a$, if $n = 2$ $T(n) = 2T(n/2) + cn$ if $n > 2$ Use induction to prove that ...
2
votes
1answer
30 views

Proof by induction regarding maximum number of questions one can ask.

sorry for the pretty ambiguous title. It's otherwise hard to describe this problem without stating it in full. There are $n$ points drawn on a whiteboard. Between every pair of points $X$ and $Y$ ...
-2
votes
1answer
49 views

Prove $2n+3 \le 2^n$ for all integers $n \ge 4$.

I have already started the problem but I am unsure on how to proceed. Prove $2n+3 \le 2^n$ for all integers $n \ge 4$. Base Case: Choose $n = 4$. $2n + 3 \le 2^n$ $2(4) + 3 \le 2^4$ $8 + 3 \le ...
1
vote
0answers
20 views

Proof modular equality by induction

I'm trying to prove using induction that $5^{2^{x-2}} = 1 + 2^x (\mod(2^{x+1}))$ So far, I have: Base case: $x = 2, 5 = 5 (\mod 8)$, It is true. $x = 3, 25 = 9 (\mod 16)$, It is true. Inductive ...
1
vote
1answer
16 views

Question on induction and the application of an 'equivalent' induction hypothesis.

I am working on the following problem which I decided to solve by induction Problem: Let $(a_n), (b_n)$ be sequences for $n \geq 1$. Define $B_n:= \sum_{i=1}^n b_n$ for $n \in \mathbb{N}$. Show ...
0
votes
1answer
32 views

Stuck at this induction problem

I am giving it everything, but i just can't get it right. The problem: Prove by induction that $n!>2^n$ for all integers $n\ge4$ I know how to solve the basic induction problems, but no matter ...
1
vote
2answers
32 views

Proof by induction for $ 2^{k + 1} - 1 > 2k^2 + 2k + 1$ for $k > 4$

I was given this proof for hw. Prove that $ 2^{k + 1} - 1 > 2k^2 + 2k + 1$ So, far I've gotten this Basis: $k = 5$, $2^{5 + 1} - 1 > 2\cdot5^2 + 2\cdot5 + 1$ => $63 > 61$ (So, the basis ...
0
votes
0answers
15 views

What is the growth of $T(n)=aT\left(\left\lfloor\sqrt[k]{n}\right\rfloor\right)+b\log(n)$

What is the growth of $T(n)=aT\left(\left\lfloor\sqrt[k]{n}\right\rfloor\right)+b\log(n)$ where $a$ and $b$ are positive reals and $k \ge 2$ is an integer? This is a generalization of my answer to ...
2
votes
2answers
59 views

Find recurrence relation of $T(n)=2T\left(\left\lfloor\sqrt{n}\right\rfloor\right)+\log(n)$

Sorry about the formatting of the title I'm not sure of the codes to make it look better. I need to find the recurrence relation of the following: $$T(0) = 1$$ $$T(n) = ...
2
votes
3answers
52 views

For every integer $n \geq 1$, prove that $3^n \geq n^2$.

It's been a while since I've done induction, and I feel like I'm missing something really simple. What I have is this: Base Case: $n=1$ $$3^n \geq n^2 \implies 3 \geq 1$$ Inductive ...
0
votes
1answer
28 views

Calc I limit/series question

Let $f : \mathbb R\rightarrow\mathbb R$ be a function that is differentiable at zero and such that $f(0)=0$. Show that for each $n\in \mathbb N$ we have that ...
1
vote
0answers
20 views

Harmonic numbers, proof that h2^k >= 1+(k/2) with induction

I'm just starting with the concept of proving mathematical statements with induction. The complete exercise with solution can be found under: ...
0
votes
1answer
38 views

Show for any integer $k \geq 1$ can be uniquely expressed as $k = 2^x + i2^{x+1}$

Show for any integer $k \geq 1$ can be uniquely expressed as $k = 2^x + i2^{x+1}$ for $i,x \geq 0$ and $i,x \in \mathbb{N}$ My attempt was to prove it inductively: $k = 1$, true assume true for $k = ...
1
vote
1answer
40 views

Strong Induction Proof / Algebra

Alright, I pretty much have the proof done, now just trying to do the algebra on it. This is the question... The information I have is: $$a_k = C_1 r^k + C_2 s^k$$ $$a_{k-1} = C_1 r^{k-1} + C_2 ...
-1
votes
1answer
29 views

The sum of powers of two

While doing a proof of correctness for an algorithm, I ran into a roadblock with a smaller proof. The problem in words: A set with all elements which are a power of 2, and the sum of the set is ...
0
votes
1answer
22 views

Proof: Probability using Induction

You have $n$ coins $C_1$, $C_2$, ..., $C_n$ for $n \in \mathbb{N}$. Each coin is weighted differently so that the probability that coin $C_i$ comes up heads is $\frac{1}{2i + 1}$. Prove by induction ...
2
votes
1answer
28 views

Gossip problem proof by induction

Question Suppose there are $n$ people in a group, each aware of a scandal no one else in the group knows about. These people communicate by telephone; when two people in the group talk, they ...
0
votes
3answers
24 views

Proof formula with induction

How can I prove by induction that $\forall n\in\mathbb{N}: \ 3^{2n} - 1$ is divisible by $8$. Proof for $n=1$: $\displaystyle3^{2\cdot1} - 1 = 8$ which is divisible by $8$. How can I prove it for ...
0
votes
1answer
29 views

Find a formula for… (Induction and Recursion)

a)Find a formula for $$\frac 1 2 + \frac 1 4 + \frac 1 8 + \cdots + \frac1{2^n}$$ by examining the values of this expression for small values of $n$. b) Prove the formula you conjectured in part a. ...
-2
votes
2answers
54 views

Proof By Induction? (Need help!) [closed]

You have to prove the following using proof by induction. Prove that $\sqrt n < \dfrac{1}{\sqrt 1} + \dfrac{1}{\sqrt 2} + \dfrac{1}{\sqrt 3} + ... + \dfrac{1}{\sqrt n}$ for $n\geq 2$.
1
vote
3answers
53 views

Hard Mathematical Induction [duplicate]

I have a mathematical induction question and I know what I need to do just not how to do it. The question is: Prove the equality of: $$(1 + 2 + . . . + n)^2 = 1^3 + 2^3 . . . + n^3$$ Base ...
0
votes
2answers
61 views

How do i prove these type of questions? I am Really stuck.

How do I solve this textbook question: If we let $n\geq 1$ be an integer and define $A_n$ to be the number of bitstrings of length $n$ that do not contain $101$ How do I determine $A_1$, $A_2$, ...
1
vote
1answer
46 views

How can I solve this recursion question, I am really stuck. [duplicate]

I am doing a couple of exercise questions, How do I show that if we let $n \geq 1$ be an integer, and if we consider $n$ people $P_1$,$P_2$,...,$P_n$. If we let $A_n$ be the number of ways these $n$ ...
0
votes
1answer
40 views

prove conjunction of consecutive implications

$n\ge 2,p_1,p_2,p_3,...,p_n,p_{n+1}$ are statements. Prove $(p_1\rightarrow p_2)\wedge (p_2\rightarrow p_3)\wedge ...\wedge (p_n\rightarrow p_{n+1})$ $\Rightarrow (p_1\wedge p_2\wedge ...
0
votes
0answers
39 views

Prove $ 2n-1=\frac{n}{3}({4n}^{2} -1)$ using mathematical induction [closed]

Prove using Mathematical induction $ 2n-1=\frac{n}{3}({4n}^{2} -1)$ for all natural numbers. I said let $P(n)$ be the statement above for $n=1$ $2(1) -1 = 1 $ and $\frac{1}{3}({4(1)}^{2} ...
2
votes
5answers
84 views

Prove that $\left(\sum_{k=1}^{n}k\right)^2=\sum_{k=1}^{n}k^3$ holds true for $n ≥ 1$

I've been trying to figure out this proof for way too long now, I'm just not sure where to begin for the inductive step. Any guidance would be greatly appreciated.
0
votes
2answers
39 views

How to verify by induction that 1(1!) + 2(2!) + … + n(n!) = (n+1)! - 1 for every pos. int. n?

Basis step: $n=1: 1(1!) = (1+1)! - 1 = 1$, true; $n=2 : 1(1!) + 2(2!) = 5 = (2+1)! - 1 = 6 - 1$, true; $n=3 : 1(1!) + 2(2!) + 3(3!) = 23 = (3+1)! - 1 = 24 - 1$, true; ... How do I prove the ...
0
votes
1answer
40 views

Prove by Induction : $\sum n^3=(\sum n)^2$ [duplicate]

I am trying to prove that for any integer where $n \ge 1$, this is true: $$ (1 + 2 + 3 + \cdots + (n-1) + n)^2 = 1^3 + 2^3 + 3^3 + \cdots + (n-1)^3 + n^3$$ I've done the base case and I am having ...
1
vote
1answer
81 views

combination/induction question, number of ways you can divide n people into groups of 1 or 2

this is homework!! Let $n \geq 1$ be an integer and consider $n$ people $P_1,P_2,\ldots,P_n$. Let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group ...
4
votes
1answer
71 views

Proof by counter example of optimal solution for Coin Changing problem (no nickels)

I'm a tutoring a student whose working on the classical coin changing problem. For those who are unfamiliar with problem or the greedy algorithm used for it. The goal is find the fewest number coins ...
0
votes
0answers
23 views

Proof of the commutativity of addition

I am trying to prove the commutativity of addition as I am trying to construct the basic algebraic properties of the natural numbers via Peano's axioms. For each $x$, $y$ is an element of the natural ...
2
votes
2answers
35 views

Proving a Recursion Using Induction

I am trying to prove the following recursion. $$a(n) = \left\{\begin{matrix} n(a(n-1)+1) & \text{if } n \geq 1\\ 0 & \text{if } n = 0 \end{matrix}\right.$$ is the series definition of ...
5
votes
2answers
39 views

Is this induction proof correct?

Question: Prove by means of the principle of induction that for every $n ∈ N$ the number $n^{3} + 2n$ is divisible by $3$. Proof Denote "$n^{3} + 2n$ is divisible by 3" by $P(n)$. Check $P(n)$ for ...
0
votes
4answers
47 views

Method of Proof (Computer Science) [duplicate]

Prove that $1+r+r^{2}+...+r^{n-1}=\frac{r^{n}-1}{r-1}$, $r$ a positive integer, $r \neq 1$