Tagged Questions

24 views

60 views

geomtry and induction Discrete Math

Claim: Suppose that we draw any number of straight lines in the plane, with the restriction that no two are parallel and no intersection point belongs to more than two lines. The lines divide up the ...
30 views

Strong induction proof with polygon

How can we show that if a simple polygon with at least four sides is triangu-lated, then at least two of the triangles in the triangulation have two sides that border the exterior of the polygon using ...
55 views

Proof related with mathematical induction

I tried to prove this claim using mathematical induction. $a^2 + 15a + 5 ≤ 21 a^2$ $\;\; ∀a∈\mathbb Z^+$ The way is as the following: Basis: for a = 1 is true since 21 = 21 Inductive step: If ...
83 views

the concept of Mathematical Induction

I am currently taking Discrete Mathematics and while I understand most of the topics covered, the one topic which I still don't quite understand is Mathematical Induction. The way the professor taught ...
27 views

Induction: Basis step question? Possibly a silly question.

The other day I learn't about Induction, and though I have a good understanding of it, I have come to a problem in an assignment. To be clear I am not looking for an answer. Also the actual question ...
20 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}$ ...
102 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: ...
29 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 ...
43 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 ...
59 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. ...
39 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 ...
41 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 ...
117 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 ...
71 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 ...
26 views

Induction Proofs

C1 = 0, Cn = 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 you do the ...
132 views

Show that the an integer $n$ is divisible by 3 if and only if the sum of its digits is divisible by 3. [closed]

Show that the an integer $n$ is divisible by 3 IFF the sum of its digits is divisible by 3, and repeat the problem for 9.
48 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$?
93 views

Induction: $n + 3 < n!$ for all $n>3$

I have a proof that I am trying to prove and I am getting stuck at the inductive hypothesis. This is my theorem: For all real numbers $n>3$, the following is true: $n + 3 < n!$. I have ...
48 views

82 views

Prove the Number of Additions of Fibonacci Number Algorithm

I am studying for a final exam and I'm having trouble with this question: The following recursive algorithm FIB takes as input an integer $n \ge 0$ and returns the $n$-th Fibonacci number $F_n$: ...
45 views

The Question: For all integers $n ≥ 1$ prove $1+2^1 +2^2 +\dots+2^n = 2^{n+1} −1$. I am having a hard time with this. when I let $n=1$, my base step is false. What do I do now?
77 views

I have 3 math induction proofs I have been struggling with for a while. I understand how to do summation proofs but these ones, I cant find a general pattern to solve. Please help. 1) $D(n) = {n(n-3) ... 3answers 221 views Use mathematical induction to prove that 9 divides$n^3 + (n + 1)^3 + (n + 2)^3$; Looking for explanation, I already have the solution. I have the solution for this but I get lost at the end, here's what I have so far. basis$n = 0$;$9 \mid 0^3 + (0 + 1)^3 + (0 + 2)^2 ?9 \mid 1 + 8$= true Induction: Assume$n^3 + (n + ...
Consider the sequence defined by $a_1 = 1$, $a_2 = 2$ and for $n\geq 3$, $a_n$ = $(a_{n-1} + a_{n-2})/ 2$. How can I use induction to prove that $|a_n - a_{n+1}|\leq 1/ 2^{n-1}$? And {$a_n$} is not a ...