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

0
votes
1answer
30 views

Use induction to prove for all $n \ge 1$, if $f(x) = ax^n$ then$ f '(x) = anx^{n-1}$.

So for the base case: $n=1$ $$F'(1) = a(1)x^0 = a$$ So this checks out. So I can assume: $f(x) = ax^k$ then $f'(x) = a\ k\ x^{k-1}$ For the induction $n = k+1$. $f'(x) = a(k+1)\ x^{(k+1)-1}$ ...
2
votes
2answers
85 views

Proofs with Induction Imply Proofs Without Induction?

Assume we can prove $\forall x P(x)$ in first order Peano Arithmetic (PA) using induction and modus ponens. Does this mean we can prove $\forall x P(x)$ from the other axioms of PA without using ...
0
votes
1answer
70 views

Proof by induction; simplify when adding k+1th term. Understanding induction.

I want to prove: $$(-\frac{1}{2})^0 + (-\frac{1}{2})^1 + \cdots + (-\frac{1}{2})^k + (-\frac{1}{2})^{k+1} = \frac{2^{k+1}+(-1^k)}{3\cdot2^k} + (-\frac{1}{2})^{k+1}$$ How do I simplify the last bit, ...
1
vote
1answer
288 views

Prove a summation inequality by induction

I was having trouble proving by induction with this problem. $$\sum_{i=1}^n \frac{3}{4^i} < 1$$ for all $n \geq 2$ I went to see my professor and he said try proving this equality ...
2
votes
4answers
90 views

Prove that for $n\ge 8$ there are nonnegative integers x and y s.t $3x+5y=n$

Prove that for every integer $n\ge 8$ there are nonnegative integers $x$ and $y$ such that $3x+5y=n$ Attempt: First of all I want to make it clear whether zero is a nonnegative integer. It ...
1
vote
1answer
248 views

Prove by minimum counterexample that $2^n>10n$ for $n>5$

Prove by minimum counterexample that for all integers $n>5$ the statement $2^n>10n$ is true. Attempt: Let $S$ be a set of counterexamples, $S=\{n \in \mathbb{Z_+}: 2^n \le 10n, \space ...
3
votes
1answer
761 views

Combinatorics - Catalan numbers recursive function proof by induction help

I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number). For $n=1$ this is true. Assume it is true for $n=k$: ...
-1
votes
1answer
80 views

Why is this proof by induction incorrect? [closed]

Let $P(n)$ be the statement "$\sum_{i=1}^{n}i=\frac{(n+\frac{1}{2})^2}{2}$". Basis Step: Clearly $P(1)$ is true as the formula holds for $n=1$. Inductive Hypothesis: Suppose that $P(k)$ is true for ...
0
votes
1answer
73 views

Is this horse proof by induction okay? [duplicate]

Let $P(n)$ be the statement "all horses in a set of n horses are of the same colour." Basis Step: Clearly, $P(1)$ is true. Inductive Hypothesis: Suppose that $P(k)$ is true for some arbitrary ...
2
votes
1answer
94 views

Use induction on $n$ to prove that $2n+1<2^n$ for all integers $n≥3$.

Use induction on n to prove that $2n+1<2^n$ for all integers $n\geq 3$. My attempt: Let $P(n)$ be the statement $2n+1<2^n$. Base case: Prove that $P(3)$ is true. $LS = 2(3)+1=7$ and ...
2
votes
2answers
280 views

Proof by Induction - Triangles

Given n non-parallel lines such that no three intersect at a point, there are n choose 3 triangles formed. So far what I come up with is by using proof by induction: ...
3
votes
1answer
71 views

How to get the garage to work. (parking functions)

At McGeorge's garage every driver has a favourite parking spot. Parking spots are arranged in a line and are numbered 1 through n. A driver always goes to his favourite spot, if it's free he takes it. ...
0
votes
1answer
44 views

Prove using mathematical induction that for every positive integer n, $\sum_{i=1}^n ( i * 2^i ) = (n-1) 2^{n+1} + 2 $

Prove using mathematical induction that for every positive integer n, $$\sum_{i=1}^ni2^i=(n-1) 2^{n+1} + 2$$ There is what i did so far :
0
votes
2answers
104 views

Using induction to prove $a_n >2^n$

For the sequence $a_n=2a_{n-1}+1$ where $a_0=1$ Show that $a_n>2^n$ using induction. Use proof by contradiction (minimum counterexample). Attempt: 1. I assume, that ...
3
votes
2answers
110 views

Argument over an induction proof

My friend gave me a problem. Define a sequence $\langle a_n \rangle$ by the recurrence relation :$$ a_{n+2} - 6a_{n+1} + 8a_n = 0 $$ and $a_1 = 4, a_2 = 8 $. Find the general term $a_n$ in ...
0
votes
1answer
59 views

Weighted Union Find

Prove that the weighted union (w_union) takes O(log2(n)) for FIND in the worst case on a graph which has n nodes by proving by induction. I'm not sure how I would prove this at all, I know how I ...
2
votes
1answer
643 views

Exponential lower bound for Fibonacci numbers

Can someone show me how to solve through induction, $F(N) \geq (3/2)^N$ for all $N\geq N_0$, where $F(n)$ is the Fibonacci function and $N_0$ is some positive integer. I know that $N_0$ should be ...
-1
votes
1answer
36 views

Induction Help Proving Statement

Help please! How do I prove: $$ C_n\leq 4(n−1)^2,\forall n\geq1. $$ Reference sequence: Sequence $C_1,C_2,..$ defined as $C_1=0$ $C_n=4C_{\lfloor n/2 \rfloor}+n,\forall n>1$ Induction ...
4
votes
2answers
149 views

After Round Robin, there is always a player such that every other was either beaten by him or beaten by a player beaten by him

Every participant of a tournament plays with every other participant exactly once. No game is a draw. After the tournament, every player makes a list with the names of all the players, who either were ...
1
vote
1answer
88 views

Am I correctly identifying the fallacy in this induction “proof?”

The prompt states: Let us accept as true that a person can always walk an extra mile. Does the Principle of Induction then prove that a person can walk forever? Where is the fallacy? No. ...
1
vote
2answers
203 views

Proof by Strong Induction involving floors and logs.

Consider the recurrence relation $a_1=1$, $a_n=na_{\lfloor n/2\rfloor}$ for $n\geq 2$. Prove using strong induction, that $a_n\leq n^{\log_{2}n}$. I am struggling to see how to deal with the ...
1
vote
1answer
99 views

Inductive Definition of regular expression

Give an inductive definition of regular expressions that do not use the star operator. Prove by induction on this definition that every such expression denotes a finite language not containing lambda. ...
0
votes
1answer
53 views

help on manipulating this algebraic expression

So I have something like: $\frac {k!}{(k-3)!3!}$ I'm going to add $\frac 12k(k-1)$ to this, and I want to obtain $\frac {(k+1)!}{(k-2)!3!}$ as the result. I'm having trouble with this since I need ...
2
votes
4answers
169 views

Recurrence sequence limit

I would like to find the limit of $$ \begin{cases} a_1=\dfrac3{4} ,\, & \\ a_{n+1}=a_{n}\dfrac{n^2+2n}{n^2+2n+1}, & n \ge 1 \end{cases} $$ I tried to use this - $\lim ...
0
votes
1answer
280 views

induction to prove regualr expression

Prove that is if S and T are any regular expressions over the one-letter alphabet, (for example: Σ = {a}), and if n is any natural, then the languages (ST)^n and (S^n)(T^n) are equal. I have to use ...
1
vote
2answers
121 views

How to solve this linear algebra problem using mathematical induction

please consider this question: Let $S,T$, be two linear transformations such that $ST-TS=I$. Prove that $ST^n-T^nS=nT^{n-1}$ for all $n\ge 1$. thanks
3
votes
1answer
110 views

Inductive hypothesis vs induction hypothesis

I'm doing a proof by induction. Should I refer to induction hypothesis or to inductive hypothesis in the proof?
2
votes
3answers
178 views

Prove that $\sum^n_{k=1} k^2 = \binom{n+1}{2} + 2\binom{n+1}{3}$ for $n\geq 2$

Prove, for all $n\geq 2$ that $$\sum^n_{k=1} k^2 = \binom{n+1}{2} + 2\binom{n+1}{3}$$ Let us prove the inductive base for $n = 2$ $$\rm{LHS} = 1^2 + 2^2= 1 + 4 = 5$$ $$\rm{RHS} = \binom{3}{2} + ...
1
vote
1answer
134 views

Proof by induction that fibonacci sequence are coprime

I have a bit difficulty to proofe that two consecutive numbers are coprime. I have the following The property $P(n)$ is the equation $(F_{n+1},F_n)=1$ where F_i the sequence of fibonacci is and $n ...
2
votes
1answer
46 views

Proof by induction for divisibility

I have to proof that $(a^n-1)$ is divisible by $(a-1)$ where $a \in \mathbb {N_{>1}}$ I think that I have the proof but I am not sure if that is the correct format. Induction hypothesis: ...
1
vote
5answers
69 views

$(x - 1)|(x^n -1); \forall x \neq 1 $ by induction.

I am just hoping to get some help on this question. Show that: $$\forall x \neq 1; (x - 1)|(x^n -1)$$ I am trying to prove this by induction on $n$. Here is what I have so far: $ \forall x \neq 1; ...
1
vote
2answers
69 views

Basic induction proof that all natural numbers can be written in the form $2a + 3b$

The theorem given is: If $n$ is a natural number then $n$ can be written in the form $2a + 3b$ for some integers $a$ and $b$. How would I prove this by induction? I've had a go at proving this ...
3
votes
5answers
49 views

$\sum_{i=1}^n \frac{1}{i(i+1)} = \frac{3}{4} - \frac{2n+3}{2(n+1)(n+2)}$ by induction.

I am wondering if I can get some help with this question. I feel like this is false, as I have tried many ways even to get the base case working (for induction) and I can't seem to get it. Can ...
0
votes
1answer
667 views

induction triangle question prove x triangles are formed

Prove with induction: Given n non parallel lines such that no three intersect at a point, there are c(n,3) triangles formed. so I have n!/(n-3)!3! triangles if this condition holds, that is all I ...
4
votes
4answers
152 views

Prove that $1+a+a^2+\cdots+a^n=(1-a^{n+1})/(1-a)$.

I have problem. Prove this using Mathematical Induction. I am a newbie in Mathematics. Please help me. $$1+a+a^2+\cdots+a^n = \frac{1-a^{n+1}}{1-a}$$ This is my way for get the proof Basic ...
1
vote
1answer
347 views

Frobenius coin problem, 5 and 9

I am hoping to get some help with two problems related to Forbenius coin problems. A) A fictional government has decided to issue currency in only 5 and 9 value denominations. Prove that there is a ...
3
votes
3answers
114 views

When is first order induction valid?

Assume we know $\forall x(P(x))$ is true in a model of Peano arithmetic (PA). Does this mean we can prove $\forall x(P(x))$ using induction? If not, why not? If $P(x)$ is true for all $x$ then $P(0) ...
2
votes
1answer
349 views

Cutting a rectangle into squares

A carpenter has a rectangular board, $x$ feet long and $y$ feet wide, with total area $n = xy $square feet. The board is to be divided into n squares (each 1 foot x 1 foot) by successively cutting a ...
1
vote
2answers
78 views

induction proof of a determinant $n \times n$

I have to proof the following property: Can somebody help my with a few steps for n=n+1? Thanks in advance. Cheers.
1
vote
3answers
82 views

Prove by induction that $3\mid (n^3 - n)$

I'm having an argument with my professor whether my exam was right or not. Before I sign a formal complain to get a review on my exam, I'd like to be sure it's correct. My answer: Proof by induction: ...
0
votes
1answer
33 views

Show that $2^{2^{n+1}-1} +1 \le 2^{2^n}$

I tried an inductive proof but it didn't work out and I'm stuck for ideas.
1
vote
1answer
49 views

Induction proof that if $C_1 = 0$ and $C_n = 4C_{\lfloor n/2 \rfloor} + n$ then $C_n \le 4(n-1)^2$

$C_1 = 0$, $C_n = 4C_{\lfloor n/2 \rfloor} + n$ Prove that $Cn$ less than or equal to $4(n - 1)^2$ What I did: Base step: n = 1 $C1$ <= $4(1 - 1)^2$ 0 <= 0 therefore true how do ...
0
votes
2answers
274 views

Use product rule and mathematical induction to show that $f^n$ is differentiable on $I$

Suppose that $f$ is differentiable on $I$. Use the product rule and mathematical induction to show that $f^n$ (the function f is raised to the nth power) is differentiable on $I$ for every positive ...
0
votes
2answers
28 views

Prove by induction that a^n+a^-n is an integer.

I am to prove by induction that given that $a+1/a$ is an integer (i.e. belongs to Z ) then $a^n+1/a^n$ is an integer too. I'm pretty much clueless here. Thanks in advance.
2
votes
2answers
129 views

Most unusual form of mathematical induction

After reading the algebraic proof of Fundamental Theorem of Algebra, where induction was carried out on "The highest power of $2$ dividing $n$", which I regard to be unusual and brilliant at the same ...
-1
votes
1answer
58 views

Prove by induction $n^3 < 3^n$. What is the value of $n_0$? [closed]

Prove by induction for $n \geq n_0$, $n^3 < 3^n$. What is the value of $n_0$?
1
vote
1answer
81 views

Induction proof strategy - backward induction

Normally, when using induction, I assume a statement is true for n, then I will try to show the same statement is also true for n+1. In the problem I have now, is is correct if I assume a statement ...
1
vote
1answer
2k views

Proof by induction Involving Factorials

My "factorial" abilities are a slightly rusty and although I know of a few simplifications such as: $(n+1)\,n! = (n+1)!$, I'm stuck I have to prove by induction that: $$\sum_{i=1}^n\frac{i-1}{i!} = ...
3
votes
4answers
154 views

Proof: $2^{n-1}(a^n+b^n)>(a+b)^n$

If $n \in \mathbb{N}$ with $n \geq 2$ and $a,b \in \mathbb{R}$ with $a+b >0$ and $a \neq b$, then $$2^{n-1}(a^n+b^n)>(a+b)^n.$$ I tried to do it with induction. The induction basis was no ...
0
votes
1answer
54 views

Induction of graphs ????

For a graph theoretical purposes, the n-dimensional cube Q_n is a simple graph whose vertices are the 2^n points (x_1... x_n) in R^n. So that for i in [n] either x_i=1 or 0, and in which two vertices ...